题解 P3566 【[POI2014]KLO-Bricks】
首先不考虑左端点和右端点的话，一个显然的贪心思路就是，每次取除了上次取的之外剩下最多的，这样会让取得更均匀，在有解的情况下一定不会出现相邻重复的现象，如果中途发现没法取了那就说明无解。
但是要是有了左右端点咋办？我们先在最左边把左端点填上，然后在按照上面的步骤贪心。但是这就会造成一个问题就是填到最右面的时候，和右端点产生冲突了，这样就会很尴尬。为了避免这种情况，我们应该贪心的把剩下的右端点砖块尽量填在最左边（先用完），这样就不会冲突了。
这个模拟我是拿权值线段树实现的，当然大概也可以拿堆什么的维护（不过感觉堆不太好修改，因为我们为了避免取到上一个填的，就暂时把上一个的个数设为-inf，而且还要修改填完了的个数反正一直以来我的堆都是拿线段树写的线段树大法好）
哦，对了，一定要注意左右端点相同的情况，貌似这题10个测试点中有6个都是左右端点相同的，被这个坑了半天……
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf -1234567890
using namespace std;
char buf[100000000];int ptr=0;
inline char get_char(){
ptr++;return(buf[ptr-1]);
}
#define getchar get_char
inline int get(){
int n;char c;while((c=getchar())||1)if(c>='0'&&c<='9')break;
n=c-'0';while((c=getchar())||1){
if(c>='0'&&c<='9')n=n*10+c-'0';
else return(n);
}
}
typedef struct _n{//线段树
int left;int right;int maxn;int pos;
}node;node memchi[3000001];int gn=1;
int ints[1000001];
inline void up(int tree){
int ls=memchi[tree].left,rs=memchi[tree].right;
if(memchi[ls].maxn>memchi[rs].maxn){
memchi[tree].maxn=memchi[ls].maxn;memchi[tree].pos=memchi[ls].pos;
}else{
memchi[tree].maxn=memchi[rs].maxn;memchi[tree].pos=memchi[rs].pos;
}
}
int build(int l,int r){//建树
int tree=gn;gn++;
if(l==r){
memchi[tree].maxn=ints[l];memchi[tree].pos=l;
}else{
int mid=(l+r)>>1;memchi[tree].left=build(l,mid);
memchi[tree].right=build(mid+1,r);up(tree);
}return(tree);
}
int pt,num;
void setpt(int l,int r,int tree){//点修改
if(l==r){
memchi[tree].maxn=num;return;
}int mid=(l+r)>>1;
if(pt<=mid)setpt(l,mid,memchi[tree].left);
else setpt(mid+1,r,memchi[tree].right);up(tree);
}
int ans[1000001];//答案
void print(int num){
if(num>=10)print(num/10);putchar(num%10+'0');
}
int main(){
fread(buf,1,100000000,stdin);
int n=get(),l=get(),r=get();int sum=0;
for(register int i=1;i<=n;i++){
ints[i]=get();sum+=ints[i];if(!ints[i])ints[i]=inf;
}
if(l==r){//特判左右端点相同可能造成的无解情况
if(ints[l]<2){
cout<<0;return(0);
}
if(sum==2){
cout<<0;return(0);
}
}sum--;
ints[r]--;if(!ints[r])ints[r]=inf;int ptr=0;
int root=build(1,n);int lst=l,lbd=ints[l];
ans[ptr]=l;ptr++;sum--;
if(l==r){//如果左右端点相同的话，因为我是用ints[r]直接看右端点还剩了多少个，所以左边填了一个后应该把这个再减1，不加这个的话只能得40分
ints[l]--;if(ints[l]==0)ints[l]=inf;
}
while(sum){
if(ints[r]>0&&lst!=r){//如果右端点没用完的话且能填上，就填右端点，因为我们要尽量的先用完右端点
ans[ptr]=r;ptr++;
pt=lst,num=lbd-1;if(num==0)num=inf;setpt(1,n,root);
lst=r;lbd=ints[r];sum--;ints[r]--;if(ints[r]==0)ints[r]=inf;
}else{
pt=lst;num=inf;setpt(1,n,root);
int me=memchi[root].pos,dat=memchi[root].maxn;
if(dat==inf){//填不了了就无解
cout<<0;return(0);
}
ans[ptr]=me;ptr++;sum--;
pt=lst;num=lbd-1;if(num==0)num=inf;setpt(1,n,root);
lst=me;lbd=dat;
}
}
for(register int i=0;i<ptr;i++){
print(ans[i]);putchar(' ');
}print(r);
return(0);
}