POJ1456贪心（set或者并查集区间合并）

题意：
给你n商品，每个商品有自己的价值还有保质期，一天最多只能卖出去一个商品，问最大收益是多少？

思路：
比较好想的贪心，思路是这样，每一次我们肯定拿价值最大的，至于在那天拿当然是尽可能的往后拖了，因为可以把前面的时间留给一些快过期的用，这种贪心策略很容易想到，对于实现的时候我尝试了两种方法，首先把商品按照价格从大到小排序，一个是我以前常用的set容器，他可以直接取出一个大于等于x的最小值（只要加上符号功能就是取最小的最大了），先把所有的天数都当成资源放进set里，然后对于没一个物品，如果可以买的话，那么就消耗离他保质期最近的那个没有备用的天，这样就行了，总的时间复杂度应该是O(n*log(n))的，可以接受，第二个方法我是用的并查集来处理区间合并，思路都是一样，就是在处理资源（天）的时候用并查集优化时间，比如一开始一个区间 1 2 3 4当第3天用了之后那么第三天就和第2天合并算一天了 1 2 4，就是这样每个天数的祖宗存的就是他左侧第一个没有用过的天数。这样写的话，如果用上路径压缩时间复杂度是O(n)的，比set快不少，如果不用路径压缩时间在逻辑上是O(n*n)的，但是刚刚我测试了下，跑了200+ac了。哎！这不重要。呵呵。

并查集+贪心 79ms
#include<stdio.h>
#include<algorithm>

#define N 10000 + 10

using namespace std;

typedef struct
{
int p ,d;
}NODE;

NODE node[N];
int mer[N];

bool camp(NODE a ,NODE b)
{
return a.p > b.p;
}

int finds(int x)
{
return x == mer[x] ? x : mer[x] = finds(mer[x]);
}

int main ()
{
int n ,ans ,i ,max;
while(~scanf("%d" ,&n))
{
max = 0;
for(i = 1 ;i <= n ;i ++)
{
scanf("%d %d" ,&node[i].p ,&node[i].d);
if(max < node[i].d) max = node[i].d;
}
for(i = 0 ;i <= max ;i ++)
mer[i] = i;
ans = 0;
sort(node + 1 ,node + n + 1 ,camp);
for(i = 1 ;i <= n ;i ++)
{
int x = finds(node[i].d);
if(!x) continue;
int y = finds(x-1);
mer[x] = y;
ans += node[i].p;
}
printf("%d " ,ans);
}
return 0;
}

set+贪心 474ms
#include<set>
#include<stdio.h>
#include<algorithm>

#define N 10000 + 10

using namespace std;

typedef struct
{
int p ,d;
}NODE;

NODE node[N];
set<int>myset;

bool camp(NODE a ,NODE b)
{
return a.p > b.p;
}

int main ()
{
int n ,i;
while(~scanf("%d" ,&n))
{
int max = 0;
for(i = 1 ;i <= n ;i ++)
{
scanf("%d %d" ,&node[i].p ,&node[i].d);
if(max < node[i].d) max = node[i].d;
}
myset.clear();
myset.insert(0);
for(i = 1 ;i <= max ;i ++)
myset.insert(-i);
sort(node + 1 ,node + n + 1 ,camp);
int ans = 0;
for(i = 1 ;i <= n ;i ++)
{
int x = *myset.lower_bound(-node[i].d);
if(!x) continue;
ans += node[i].p;
myset.erase(x);
}
printf("%d " ,ans);
}
return 0;
}

POJ1456贪心（set或者并查集区间合并）

相关推荐