luogu[3566] Bricks

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

简单说两句

多久没写过题解了呢…

blog还要边上的h^ovny指点呢。

题目

???

思路

简单想到这是一个贪心。

每次取当前数目最多的那个数，将它放在当前位上。

如果有多个数目相同的数，那优先取最后一个数。（很明显，避免重复）

那这就好做了。数目可以用堆来维护。

（结构体还真是个恶心的东西呢。莫名RE…）

无解的情况有好多处理的方法，就不说了。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+7;
inline int read(){
	int x=0,f=1;char C=getchar();
	while(!isdigit(C)) {if(C=='-') f=-1;C=getchar();}
	while(isdigit(C)) x=(x<<1)+(x<<3)+C-'0',C=getchar();
	return x*f;
}
int ans[maxn],n,S,T,tot,a[maxn],last;
struct node{
	int id,x;
	bool operator < (const node &t) const {
		return x<(t.x)||((x==t.x)&&t.id==T);
	}
}A;
priority_queue<node>que;
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=read(),last=ans[1]=S=read(),T=read();
	for(int i=1;i<=n;i++) tot+=(a[i]=read());
	a[S]--,a[T]--; ans[tot]=T;
	for(int i=1;i<=n;i++) que.push((node){i,a[i]});
	for(int i=2;i<tot;i++){
		bool F=0;
		node u=que.top(); que.pop();
		if(u.id==last) F=1,A=u,u=que.top(),que.pop();
//		printf("%d %d\n",u.id,u.x);
		if(F){
			if(u.id==A.id) {cout<<0;return 0;}
			else que.push(A);
		}
		ans[i]=u.id; u.x--;if(u.x>0) que.push(u); last=u.id;
	}
	int F=1;
	for(int i=2;i<=tot;i++) if(ans[i]==ans[i-1]) F=0;
	if(F){
		printf("%d",ans[1]);
		for(int i=2;i<=tot;i++) printf(" %d",ans[i]);
	} else cout<<F;
	return 0;
}

时间一久了，码风都变了呢。

希望能过，再%一下Venus大佬。

谢谢观看。