[POJ 1456] Supermarket【贪心 / 贪心+优先队列 / 贪心+并查集】

• 2018-01-04
• 0
• 0

Problem:

Description

A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell ≤ Prod such that the selling of each product x∈Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)=Σ_x∈Sellpx. An optimal selling schedule is a schedule with a maximum profit.
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(Tn²)，并不能通过本题，然而 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(Tn²) [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;
}