ZOJ 2968 Difference Game【欲張り+二分】

  :

 Ga、Gb    ,         。                           

      ,      C。    Ga      Gb            。

  :

         ,  Ga      Gb                     。    

      。                 (     Ga ,     Gb )    

 ,          ,  Ga  Gb      ab  ,Gb   Ga   ba  ,    

  Ga     Gb,  Gb     Ga,                  ,       

2*min(ab,ba)。                  ,          2,        

|ab-ba|*(|ab-ba|-1)。     2*min(ab,ba) + |ab - ba| *(|ab -ba|- 1)。

            ,Ga           Gb      ,        Ga  C/2

(C/2+1)     Gb ,Gb  C/2+1(C/2)   Ga ,      。

By @sake

　　
Source Code:

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler

#include <stdio.h>

#include <iostream>

#include <fstream>

#include <cstring>

#include <cmath>

#include <stack>

#include <string>

#include <map>

#include <set>

#include <list>

#include <queue>

#include <vector>

#include <algorithm>

#define Max(a,b) (((a) > (b)) ? (a) : (b))

#define Min(a,b) (((a) < (b)) ? (a) : (b))

#define Abs(x) (((x) > 0) ? (x) : (-(x)))

#define MOD 1000000007

#define pi acos(-1.0)



using namespace std;





int ga[20010], gb[20010], gc[50000];

bool cmp(const int & a, const int &b){

    return a > b;

}

//    ,   key,   n,     -1

int b_search(int key, int n){

    int l = -1, r = n, m;

    while (l+1 < r) {

        m = (l+r)/2;

        if (ga[m] < key) {

            l = m;

        } else {

            r = m;

        }

    }

    return r;

}

int main(){

    int t;

    scanf("%d", &t);while (t--) {

        int n, cost;

        scanf("%d%d", &n, &cost);

        for (int i = 0; i < n; i ++) {

            scanf("%d", &ga[i]);

            gc[i] = ga[i];

        }

        for (int i = 0; i < n; i ++) {

            scanf("%d", &gb[i]);

            gc[i+n] = gb[i];

        }

        if (n == 1) {

            printf("%d
", ga[0] - gb[0]);

            continue;

        }

        sort(ga, ga+n);

        sort(gc, gc+2*n);

        sort(gb, gb+n, cmp);

        int maxn = -50000;

        for (int i = 1; i < 2*n; i ++) {

            int ab = b_search(gc[i], n);

            int ba = (2*n - i) - (n - ab);

            int mab = min(ab, ba);

            int fab = abs(ab-ba);

            int c = 2*mab + (fab-1)*fab;

            if (c <= cost) {

                maxn = max(maxn, gc[i]-gc[i-1]);

            }

        }

        if (maxn > 0) {

            printf("%d
", maxn);

        } else {

            int ans = max(ga[cost/2]-gb[cost/2+1], ga[cost/2+1]-gb[cost/2]);

            printf("%d
", ans);

        }

    }

    return 0;

}