首页 > 代码库 > [POJ1456]Supermarket（贪心 + 优先队列 || 并查集）
[POJ1456]Supermarket（贪心 + 优先队列 || 并查集）
传送门
1.贪心 + 优先队列
按照时间排序从前往后
很简单不多说
——代码
1 #include <queue> 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 #define N 10001 6 7 int n, t, ans; 8 std::priority_queue <int, std::vector <int>, std::greater <int> > q; 9 10 struct node11 {12 int a, b;13 }p[N];14 15 inline int read()16 {17 int x = 0, f = 1;18 char ch = getchar();19 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;20 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;21 return x * f;22 }23 24 inline bool cmp(node x, node y)25 {26 return x.b < y.b;27 }28 29 int main()30 {31 int i, j;32 while(~scanf("%d", &n))33 {34 t = 1;35 ans = 0;36 while(!q.empty()) q.pop();37 for(i = 1; i <= n; i++) p[i].a = read(), p[i].b = read();38 std::sort(p + 1, p + n + 1, cmp);39 for(i = 1; i <= n; i++)40 {41 if(t <= p[i].b)42 {43 t++;44 ans += p[i].a;45 q.push(p[i].a);46 }47 else if(t == p[i].b + 1 && q.top() < p[i].a)48 {49 ans += p[i].a - q.top();50 q.pop();51 q.push(p[i].a);52 }53 }54 printf("%d\n", ans);55 }56 return 0;57 }
2.并查集
很难想
按照价格从大到小排序
如果当前的那一天没有被占用，那么就用当前那一天，如果当前那一天被占用了，就用上一天，如果还被占用，再往前
其实这就是暴力过程
可以用并查集优化，当前天被占用时用并查集连接上一天，如果根指向0，就表明前面的天都被占用了，也就不用加
具体看代码
——代码
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define N 10001 5 6 int n, ans; 7 int f[N]; 8 9 struct node10 {11 int a, b;12 }p[N];13 14 inline bool cmp(node x, node y)15 {16 return x.a > y.a;17 }18 19 inline int find(int x)20 {21 return x == f[x] ? x : f[x] = find(f[x]);22 }23 24 inline int read()25 {26 int x = 0, f = 1;27 char ch = getchar();28 for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;29 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;30 return x * f;31 }32 33 int main()34 {35 int i, x;36 while(~scanf("%d", &n))37 {38 ans = 0;39 for(i = 1; i < N; i++) f[i] = i;40 for(i = 1; i <= n; i++) p[i].a = read(), p[i].b = read();41 std::sort(p + 1, p + n + 1, cmp);42 for(i = 1; i <= n; i++)43 {44 x = find(p[i].b);45 if(x)46 {47 f[x] = x - 1;48 ans += p[i].a;49 }50 }51 printf("%d\n", ans);52 }53 return 0;54 }
[POJ1456]Supermarket（贪心 + 优先队列 || 并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。