P3566 解题报告

· · 题解

前言

传送门，个人博客内食用更佳哦！题目链接

先膜拜一下神犇枫林晚的神仙题解，本题解是优先队列做法捏。

题意

题意在题面里已经有了，但是有坑，在此感谢一下@ydnhaha 的题解，感谢他提示的无解要输出 0。

思路分析

首先看一眼肯定是贪心，贪心怎么贪捏，就是用小的把大的隔开（用第六感的得出的）。

那为何不用小的隔开小的呢，易得如果小的把小的隔开了之后，还有剩余的砖能给大的隔完，那小的隔开大的也肯定能行，所以对于任何的情况我们都用小的隔开大的就行了（下面会给具体证明捏）。

那小的和大的如何排序捏。因为是每次操作完都要放回去重新排序，所以自然而然的想到了优先队列来每次插入后自动排序。（说实话太久没写了重载炸了好几次。）

证明

设按砖的数量从小到大排列的砖的数量分别为 a_1,a_2\ldots a_n，颜色分别为 id_1,id_2\ldots id_n。

假设一个最劣情况，即为 a_n=\sum_{i=1}^{n-1} 但是结尾不为 id_n， 开头不为 id_1。

若我用小的隔开大的，那么结果即为 id_1,id_n\ldots id_2,id_n\ldots id_{n-1},id_n 最后刚好用小的将大的隔完。

但若我用小的隔开小的，那么前面便又一堆 id_1,id_2 (a_1 个)，id_2,id_3 (a_2-a_1 个)，id_3,id_4 (a_3-a_2+a_1 个) \ldots 最后到了 id_{n-1},id_n 时便只能排列 a_{n-1}-a_{n-2}+a_{n-3}-a_{n-4}\ldots 个，又因为这里面有将近一半的项是减，所以这个值肯定小于 \sum_{i=1}^{n-1} 即为 a_n 也就是还有剩下的砖没被隔开完，没法排列了。

对于相同的一种最劣极端情况，用小的隔开大的可以成功，而小的隔开小的不行，自然要选择小的隔开小的了。

AC 代码

终于到愉快的上代码环节了(^▽^)。

（对了强调一个要点，开头和结尾时可能相同的，所以第 23 和第 24 行是不能用正常 if 的方式合并的捏。有个蠢货在这个地方卡了自己好几次。）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,b,e,tot,now;
int ans[1000010];
struct node{int id,x;};
bool operator <(node x,node y){return (x.x==y.x)?x.id!=e:x.x<y.x;}
priority_queue<node> q;
int read()//传统技艺快读
{
  char c=getchar();int x=0;
  while(!isdigit(c)) c=getchar();
  while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
  return x;
}
signed main()
{
  n=read(),b=read(),e=read();
  for(int i=1,x;i<=n;i++)
  {
    x=read();
    tot+=x;
    if(i==b) x--;
    if(i==e) x--;
    //就是上面两行，千万不能正常合并，因为b和e可能相等
    if(x>0) q.push((node){i,x});
    else if(x<0){printf("0");return 0;}
  }
  ans[1]=b,now=b;
  for(int i=2;i<tot;i++)
  {
    node t=q.top();q.pop();
    if(t.id==now)//如果最上面的一块砖的颜色和前一个一样
      if(!q.empty())//如果序列中还有砖
      {
        node t1=q.top();q.pop();//拿出另一种颜色的砖放上
        ans[i]=now=t1.id;
        if(t1.x>1) q.push((node){t1.id,t1.x-1});
        q.push(t);
        continue ;
      }
      else{printf("0");return 0;}//拿不出不同颜色的砖了，自然意味着不行了
     now=ans[i]=t.id;
     if(t.x>1) q.push((node){t.id,t.x-1});
  }
  ans[tot]=e;
  for(int i=1;i<tot;i++)
    if(ans[i]==ans[i+1]||!ans[i])//重新扫一遍有没有不符合的情况
    {
      printf("0");
      return 0;
    }
  for(int i=1;i<=tot;i++)
  {
    printf("%d",ans[i]);
    if(i!=tot) printf(" ");
  }
  return 0;
}

完结撒花 (^▽^)！！！