传送门：

 

题意：给你一个数组，你可以进行一个操作：取a[i],a[j]，且a[i]<a[j]，令d*2<=a[j]-a[i]，随后令a[i]+=d;a[j]-=d。问最后能否形成另一数组b，并输出方案

 

思路：先考虑不可能的情况，若两边和不相等，则肯定不可能。如果a数组前k个数的和大于b数组前k个数的和，则不可能，因为我们可以把前k个数看成一个整体，它在操作中只能变大不能变小。

若可能，则从小到大搜一个个消耗即可

……然而我最简单的消耗之前都写错了……

之前是这样的：把a[i]-b[i]>0的分为X组,a[i]-b[i]<0的分为Y组，然后各组加减消耗（当时居然还按照差排了个序！！！）。却没有想到X组中需要减的数可能比Y组中需要加的数还要小，因为再次排序完全打乱了从小到大的顺序

…………结果就是——比赛后删掉sort语句就AC了…………

 

略简洁代码：

1 #include
      
        2 using namespace std; 3 typedef long long ll; 4 const int inf=(int)(2e9); 5 const ll INF=(ll)(5e18); 6 const int N=450010; 7  8 ll n,sa=0,sb=0; 9 ll s1=0,s2=0,c[N];10 struct node11 {12     ll x,id;13 }fa[N],fb[N],a[N],b[N];14 vector
       
         v[3];15 16 bool cmp(node p,node q)17 {18     if(p.x==q.x) return p.id
        
         sb)50         {51             puts("NO");52             return 0;53         }54     }55     puts("YES");56     ll ans=0;57     for(int i=1,j=1;i<=n;i++)58     {59         while(c[i]<0)60         {61             ans++;62             while(c[j]<=0) j++;63             ll d=min(-c[i],c[j]);64             v[0].push_back(a[i].id);65             v[1].push_back(a[j].id);66             v[2].push_back(d);67             c[i]+=d; c[j]-=d;68         }69     } 70     cout<
         
          <