POI2014 Bricks
程序员文章站
2022-03-06 22:20:00
...
Bricks
POI2014
一开始分类讨论半天,wa的一塌糊涂,仔细想想可以贪心哇
题意
1.有n种颜色的砖块
2.第i种颜色的砖块有a[i]个(a[i]>0)
3.把他们放成一排,使得相邻两个砖块的颜色不相同,限定第一个砖块的颜色是start,最后一个砖块的颜色是end
4.请构造出一种合法的方案或判断无解。
解
1.为了达到“相邻两个砖块的颜色不相同”的目的,当然是多种颜色交替使用了。
2.每次选择剩余数目最多且不与上次重复的砖块
3.但是要防止end砖块被留到最后,我们在数目相同时优先选end颜色的
4.最后判断是否有砖块剩余
5.再判断col[n],col[n-1]颜色是否相同(因为你只保证col[i]!=col[i-1])
具体代码
#include<bits/stdc++.h>
using namespace std;
const int M=1000005;
#define fi first
#define se second
typedef pair<int,int>P;
priority_queue<P>Q;
int n,st,ed;
int cnt[M],sum,ans[M];
int main() {
scanf("%d %d %d",&n,&st,&ed);
for(int i=1; i<=n; i++) {
scanf("%d",&cnt[i]);
sum+=cnt[i];
}
ans[1]=(st==ed?M:st),ans[sum]=M;
if(n==1&&sum==1){
printf("1\n");
return 0;
}
cnt[st]--,cnt[ed]--;
if(n==1||cnt[st]<0||cnt[ed]<0) {
printf("0\n");
return 0;
}
for(int i=1; i<=n; i++) {
if(cnt[i]){
if(i==ed)Q.push(P(cnt[i],M));
else Q.push(P(cnt[i],i));
}
}
bool flag=1;
int ls=(st==ed?M:st);
int now=2;
while(!Q.empty()) {
P p1=Q.top();
Q.pop();
if(p1.se==ls) {
if(Q.empty()) {
flag=0;
break;
}
P p2=Q.top();
Q.pop();
p2.fi--;
ans[now]=p2.se;
ls=p2.se;
if(p2.fi)Q.push(p2);
Q.push(p1);
} else {
p1.fi--;
ans[now]=p1.se;
ls=p1.se;
if(p1.fi)Q.push(p1);
}
now++;
}
if(!flag||ans[sum]==ans[sum-1])printf("0\n");
else {
for(int i=1; i<=sum; i++){
printf("%d ",ans[i]==M?ed:ans[i]);
}
}
return 0;
}
上一篇: 正则化
下一篇: 在训练过程中加入Dropout