Problem retelling

There are N tasks, each task has a latest end time and a corresponding reward. If the task is completed before the end time, the corresponding reward can be obtained. The time required to complete each task is one unit of time. Sometimes it’s impossible to accomplish all the tasks, because there may be conflicts in time, which requires you to choose between them. Seek the highest reward you can get.

Standard Input

Line 1: a number N, representing the number of tasks (2 <= N <= 50000)
Line 2 ~ （N + 1）： with two numbers per line, separated by spaces in the middle, indicates the latest end time of the task E [i] and the corresponding reward W [i]. (1 <= E [i] <== 10 ^ 9, 1 <= W [i] <== 10 ^ 9)

Standard Output

The highest reward for output.

Example

Constraints

Analysis&Implement

First, the data is stored and processed. Because the C++ array definition must apply for quantitative space, it can not be changed according to the input value, so the structure container is chosen to store the data.
Secondly, greedy algorithm should be used in this problem, because the tasks are unit time, the solution is optimal.
For specific implementation, I have considered a lot of practices, and ultimately choose the “priority queue” to save the reward data.
Starting from 0, the time consumed for each task is 1, increasing by the latest time. If the latest time for the nth task is greater than the amount of time consumed, it can be counted as the total, if not greater than the amount of time consumed.
You can replace one of the tasks with the smallest reward in the total (if the reward for the current task is more).

首先，存储和处理数据。由于C++数组定义必须申请定量空间，不能根据输入值改变，因此选择结构体容器来存储数据。
其次，因为该问题的任务是单位时间的，应采用贪婪算法，获得的解应是最优的。
对于具体的实现，我考虑了很多方案，最终选择了“优先队列”来保存奖励数据。
从0开始，每完成一件任务，消耗时间为1，按最晚时间递增，第n个任务如果最晚时间大于已消耗掉时间量，则可算入总和，若不大于已耗时间量，则可以替换掉总和里最小奖励的一个任务(如果当前任务的奖励更多的话)。

#include <iostream>
#include <algorithm>    //sort()
#include <vector>       //vector<Type>
#include <queue>        //priority_queue<Type, Container, Functional>
#include <functional>   //greater<Type>
using namespace std;

struct Data {           //定义结构体变量
	long long endtime;  //终止时间
	long long reward;   //奖励
};

bool comp(const Data & a, const Data & b)   //指示sort比较的内容
{
	return a.endtime < b.endtime;
}

int main()
{
	int num;
	long long sum=0;
	cin >> num;
	vector<Data>data(num);             //创建结构体容器
	for (int i = 0; i < num; i++) {    //容器赋值
		cin >>data[i].endtime >> data[i].reward;		
	}
	sort(data.begin(), data.end(), comp);    //根据终止时间对结构体进行排序
	priority_queue<long long, vector<long long>, greater<long long> >q;  //创建优先队列
	for (int i = 0; i < num;i++) {
		int gets=data[i].reward;
		if (data[i].endtime > q.size()) {
			sum += gets;
			q.push(gets);
		}
		else {
			sum += gets;
			q.push(gets);
			sum -= q.top();
			q.pop();
		}
	}
	cout << sum;
    return 0;
}

Thanks for watching!

最后

以上就是跳跃鸵鸟为你收集整理的最高的奖励（贪婪算法）Problem retellingAnalysis&Implement的全部内容，希望文章能够帮你解决最高的奖励（贪婪算法）Problem retellingAnalysis&Implement所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。