最高的奖励
时间限制：1000 ms | 内存限制：65535 KB难度：3
- 描述
请问：挖掘机技术哪家强？AC了告诉你！
给你N（N<=3*10^4）个任务，每个任务有一个截止完成时间t（1=<t<=10^9）和完成该任务的奖励v（1=<v<=10^9）,每个任务要花一天完成，问最多能获得多少奖励？
- 输入
-
多组 测试数据。第一行一个数N，表示任务总数。接下来N行，每行两个数t和v,如上所述。
- 输出
-
对于每组数据输出最高的奖励。
- 样例输入
-
7
4 20
2 60
4 70
3 40
1 30
4 50
6 10 - 样例输出
-
230
这道题刚开始贪心没有用优先队列,是按照价值来的,但是感觉不对. 最后才知道按照天数来进行贪心.
代码如下:
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <algorithm> using namespace std;
const int N = ;
bool vis[N];
struct Node{
int day, value;
friend bool operator < (const Node a, const Node b)
{
return a.value > b.value;//value小的优先级高
}
}; bool cmp(const Node a, const Node b)//二级排序, 先按照天数来排,天数小的在前,相同天数的情况下再按照奖励大小来排,奖励大的在前
{
if (a.day != b.day)
return a.day < b.day;
return a.value > b.value;
}
int n;
Node node[N];
int main()
{
while (~scanf("%d", &n) && n)
{
for (int i = ; i < n; i++)
{
scanf("%d %d", &node[i].day, &node[i].value); }
sort(node, node + n, cmp);
priority_queue<Node> Q;
memset(vis, false, sizeof(vis));
for (int i = ; i < n; i++)
{
if (!vis[node[i].day])//如果这一天没有其它任务占有
{
vis[node[i].day] = true;
Q.push(node[i]);
}
else
{
if (Q.size() < node[i].day)//如果这一天前面有空闲的天数
Q.push(node[i]);
else
{
Node tmp = Q.top();//将它与最小值比较,如果大于添加到队列中的最小值,就要替换
if (tmp.value < node[i].value)
{
Q.push(node[i]);
Q.pop();
}
}
}
}
long long ans = ;
while (!Q.empty())
{
Node tmp = Q.top();
Q.pop();
ans += tmp.value;
}
cout << ans << endl;
} return ;
}