[POJ 1456] Supermarket【贪心 / 贪心+优先队列 / 贪心+并查集】
Problem:
Time Limit: 2000MS | Memory Limit: 65536K |
Description
For example, consider the products Prod={a,b,c,d} with (pa,da)=(50,2), (pb,db)=(10,1), (pc,dc)=(20,2), and (pd,dd)=(30,1). The possible selling schedules are listed in table 1. For instance, the schedule Sell={d,a} shows that the selling of product d starts at time 0 and ends at time 1, while the selling of product a starts at time 1 and ends at time 2. Each of these products is sold by its deadline. Sell is the optimal schedule and its profit is 80.

Write a program that reads sets of products from an input text file and computes the profit of an optimal selling schedule for each set of products.
Input
Output
Sample Input
4 50 2 10 1 20 2 30 1 7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
Sample Output
80 185
Hint
Source
Solution:
在网上找并查集的题,结果给了一道贪心题。。
这道题的贪心思路很好理解,就是先将商品按价格从大到小排序,再枚举每个商品,尝试将其放在能放的最大时间处即可。详见 Code #1。
Code #1 的最坏时间复杂度为 O(Tn2),并不能通过本题,然而 POJ 的数据实在太水,抱着必 TLE 的决心交上去竟然 AC 了。。
但不能就此罢休。浏览了一下 [discuss] 发现这题可以用优先队列优化。但是这次要按截止时间从大到小排序,然后枚举每个时间点,将这个时间点截止的商品扔进优先队列里,再取 1 次最大值(每个时间点只能卖 1 样商品)即可。详见 Code #2。
Code #2 的时间复杂度为 O(Tnlogn),这样才是正解。
突然又看到这道贪心题真的有并查集优化的方法,而且十分巧妙。可以发现 Code #1 复杂度的瓶颈是寻找“能放的最大时间”,而这个可以用并查集的特点进行优化。画图易知,每次节点 i 放过之后,将 fa[i] 设置为 i - 1,这样下次 find() 的时候就一定会跳过 i,再通过路径压缩做到快速寻找能放的最大时间。详见 Code #3。
Code #3 的时间复杂度为 O(Tnα(n)) ≈ O(Tn),效率较 Code #2 提高不少(虽然在 POJ 的水数据面前差异不太明显)。
Code #1: O(Tn2) [252K, 141MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int n, ans; bool vis[10005]; struct Product{ int val, deadl; inline bool operator < (const Product &prod2) const {return val > prod2.val;} } prod[10005]; int main(){ while(scanf("%d", &n) != EOF){ for(register int i = 1; i <= n; i++) scanf("%d%d", &prod[i].val, &prod[i].deadl); sort(prod + 1, prod + n + 1); memset(vis, 0, sizeof(vis)), ans = 0; for(register int i = 1; i <= n; i++) for(register int j = prod[i].deadl; j > 0; j--) if(!vis[j]){ vis[j] = 1, ans += prod[i].val; break; } printf("%d\n", ans); } return 0; }
Code #2: O(Tnlogn) [404K, 79MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> using namespace std; int n, ans; struct Product{ int val, deadl; inline bool operator < (const Product &prod2) const {return deadl > prod2.deadl;} } prod[10005]; priority_queue<int> q; inline void clearPQ(priority_queue<int> &q) {priority_queue<int> tmp; swap(tmp, q);} int main(){ while(scanf("%d", &n) != EOF){ int maxDate = 0; for(register int i = 1; i <= n; i++){ scanf("%d%d", &prod[i].val, &prod[i].deadl); maxDate = max(maxDate, prod[i].deadl); } sort(prod + 1, prod + n + 1); clearPQ(q), ans = 0; int prodId = 1; for(register int curDate = maxDate; curDate > 0; curDate--){ for(; prodId <= n && prod[prodId].deadl >= curDate; prodId++) q.push(prod[prodId].val); if(!q.empty()) ans += q.top(), q.pop(); } printf("%d\n", ans); } return 0; }
Code #3: O(Tnα(n)) [284K, 63MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int n, ans, maxDate; struct Product{ int val, deadl; inline bool operator < (const Product &prod2) const {return val > prod2.val;} } prod[10005]; int fa[10005]; inline void ds_init() {for(register int i = 1; i <= maxDate; i++) fa[i] = i;} inline int ds_find(const int &u){ if(fa[u] == u) return u; return fa[u] = ds_find(fa[u]); } inline void ds_union(const int &u, const int &v){ int ancu = ds_find(u), ancv = ds_find(v); fa[ancu] = ancv; } int main(){ while(scanf("%d", &n) != EOF){ maxDate = 0; for(register int i = 1; i <= n; i++){ scanf("%d%d", &prod[i].val, &prod[i].deadl); maxDate = max(maxDate, prod[i].deadl); } sort(prod + 1, prod + n + 1); ans = 0, ds_init(); for(register int i = 1; i <= n; i++){ int anc = ds_find(prod[i].deadl); if(anc) ans += prod[i].val, ds_union(anc, anc - 1); } printf("%d\n", ans); } return 0; }
发表评论