BZOJ 3523 Bricks

发表于 | 更新于

Link

Solution

贪心+模拟，每次取剩下的个数最大的，在最大的里面如果有endend，就先取endend。 被priority_queueFunctor的奇葩规则坑了一会儿。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include "lucida"
using std::pair;
using std::make_pair;
using std::priority_queue;
using std::vector;
const int MAXN=1000000+11;
int ed;
struct CmpFunctor {
	bool operator () (const pair<int,int> &a,const pair<int,int> &b) {
		return (a.first!=b.first)?a.first<b.first:(b.second==ed);	
	}//按照这个排序方式，排到后面的 优先级高 先弹出来
};
int main() {
	freopen("input","r",stdin);
	static int s[MAXN],a[MAXN];
	priority_queue<pair<int,int>,vector<pair<int,int> >,CmpFunctor> Q;
	int n,st,m=0;is>>n>>st>>ed;
	pair<int,int> pred,now;
	bool tak=1;
	for(int i=1;i<=n;++i) {
		is>>a[i];m+=a[i];
		//tak&=(i==st || i==ed)?(bool)a[i]:1;
		//写在else里面 直接排掉了st==ed的情况
		if(i==ed)
			a[i]--;
		if(i==st)
			pred=make_pair(--a[i],i);
		else 
			Q.push(make_pair(a[i],i));
		if(a[i]<0) {
			tak=0;
			break;
		}
	}
	if(n==1 && m!=1)
		tak=0;
	s[1]=st;s[m]=ed;
	for(int i=2;i<=m-1 && tak;++i) {
		now=Q.top();Q.pop();
		//os<<'<'<<now.first<<','<<now.second<<'>'<<'\n';
		if(now.first<=0) {
			tak=0;
			break;
		} else {
			s[i]=now.second;
			now.first--;
			Q.push(pred);
			pred=now;
		}
	}
	for(int i=2;i<=m && tak;++i)
		tak&=(s[i]!=s[i-1]);
	if(tak)
		for(int i=1;i<=m;++i)
			os<<s[i]<<(i==m?'\n':' ');
	else
		os<<0<<'\n';
	return 0;
}