zoj2968 Difference Game

分析：

一 首先答案可以是正数。

那就简单了，先把所有的数进行升序排列，因为ga数组最小的数一定比gb数组最大的数大。所以排列后一定会在相连的位置得到答案。所以就从左到右便利分割点。

左边作为gb数组，右边作为ga数组，然后进行原数组的模拟，然后判断下cost有没有超过c即可。

如果发现不可能为正数，那就必须是负数了。

二 负数的情况

因为每交换一对数会花费2，而且最后还可以进行一次交换（0的时候）.所以就简单了，只需要判断一对一对交换后，最后要交换的那个位置，2种情况取（就是上面最小的下来，下面最大的上去）最大的结果就可以了。奇数偶数是一样的做法。

然后，第一步取正数的过程中，因为a数组是有大小的所以可以直接二分位置。因为题目数据量不是很大，为求方便我就直接遍历了。

上代码

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; int ga[20005],gb[20005],gc[50000]; int s,c; int Max=-50006; int flag=0; void solve1(){ int i,j,k; for(i=1;i<2*s;i++){ int sum1=0,sum2=0; for(j=s-1;j>=0;j--){ if(gc[i]>ga[j]) break; else sum1++; } for(k=0;k<=s-1;k++){ if(gc[i]<=gb[k]) break; else sum2++; } int ka=s-sum1,kb=s-sum2; int temp=min(ka,kb); int cost=temp*2; int k=abs(ka-kb); cost+=k*(k-1); if(cost<=c){ flag=1; Max=max(Max,gc[i]-gc[i-1]); } } } int main() { int t; scanf("%d",&t); while(t--){ int i; scanf("%d%d",&s,&c); for(i=0;i