首页 > 代码库 > POJ 1456 (贪心+并查集) Supermarket
POJ 1456 (贪心+并查集) Supermarket
有n件商品，每件商品有它的利润和售出的最后期限，问能够得到的最大利润是多少
这道题和 HDU 1789 Doing Homework again 几乎一模一样，只不过这个是求最的扣分，本题是求最大利润
朴素的做法是：
按照每件商品的利润从大到小排序，有一个busy数组记录那天是否有东西卖出。对于每件商品，从它的截止日期开始遍历，如果那天有东西卖就看看前一天是否有卖东西，直到有一天没有东西卖或者前面的天数都有卖的。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 10000 + 10; 9 struct Product10 {11 int p, d;12 bool operator< (const Product& a) const13 {14 return p > a.p || (p == a.p && d > a.d); 15 }16 }products[maxn];17 bool busy[maxn];18 19 int main(void)20 {21 #ifdef LOCAL22 freopen("1456in.txt", "r", stdin);23 #endif24 25 int n;26 while(scanf("%d", &n) == 1)27 {28 memset(busy, false, sizeof(busy));29 for(int i = 0; i < n; ++i)30 scanf("%d%d", &products[i].p, &products[i].d);31 sort(products, products + n);32 33 int ans = 0;34 for(int i = 0; i < n; ++i)35 {36 for(int j = products[i].d; j > 0; --j)37 {38 if(!busy[j])39 {40 ans += products[i].p;41 busy[j] = true;42 break;43 }44 }45 }46 printf("%d\n", ans);47 }48 return 0;49 }
并查集优化：
POJ 1456 (贪心+并查集) Supermarket
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。