首页 > 其他 > 详细

zoj2968 Difference Game

时间:2014-04-02 09:04:14      阅读:462      评论:0      收藏:0      [点我收藏+]

分析:

一   首先答案可以是正数。

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

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

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

二  负数的情况

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


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

上代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<stack>
#include<algorithm>
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<s;i++) {
            scanf("%d",&ga[i]);
            gc[i]=ga[i];
        }
        for(i=0;i<s;i++){
            scanf("%d",&gb[i]);
            gc[i+s]=gb[i];
        }
        if(s==1){
            printf("%d\n",ga[0]-gb[0]);
            continue;
        }
        sort(ga,ga+s);sort(gb,gb+s);
        sort(gc,gc+2*s);
        flag=0;
        Max=-50006;
        solve1();
        if(flag==1) printf("%d\n",Max);
        else{
               Max=max(Max,ga[c/2+1]-gb[s-c/2-1]);
               Max=max(Max,ga[c/2]-gb[s-c/2-2]);
            printf("%d\n",Max);
        }
    }
}



zoj2968 Difference Game,布布扣,bubuko.com

zoj2968 Difference Game

原文:http://blog.csdn.net/cnh294141800/article/details/22751711

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!