BZOJ3523: [Poi2014]Bricks
それぞれの色のレンガの数をあげて、同じ色のレンガを一緒に置くことができなくて、2つの色はすでに確定して、1種の方案を構築します
欲張りだと思われがちですが、どの色が残っているかはその色を優先し、複数の色の数が同じで最後の色を優先して、どうしても入れられないと解けません
欲張りだと思われがちですが、どの色が残っているかはその色を優先し、複数の色の数が同じで最後の色を優先して、どうしても入れられないと解けません
#include
#include
#include
#define N 1000010
using namespace std;
struct ppp{int w,c;};
int st,en;
bool operator q;
int ans[N];
int main()
{
int n;
scanf("%d%d%d",&n,&st,&en);
int i,j,x,y,m=0;
ppp t,tmp;
for(i=1;i<=n;i++)
{
scanf("%d",&t.w);
m+=t.w;
t.c=i;
if(i==st) t.w--;
if(i==en) t.w--;
if(t.w<0) {puts("0");return 0;}
q.push(t);
}
ans[1]=st;ans[m]=en;
bool f;
for(i=2;i1)
q.push((ppp){t.w-1,t.c});
if(f) q.push(tmp);
}
if(ans[m-1]==ans[m]) {puts("0");return 0;}
for(i=1;i<=m;i++)
printf("%d ",ans[i]);
}