ACM - ICPC World Finals 2013 F Low Power

원제 다운로드:http://icpc.baylor.edu/download/worldfinals/problems/icpc2013.pdf
제목 번역:
문제 설명
n 개의 기계 가 있 고 기계 마다 2 개의 칩 이 있 으 며 칩 마다 k 개의 배 터 리 를 넣 을 수 있다.모든 칩 에 너 지 는 k 개의 배터리 에너지 의 최소 값 이다.두 칩 의 에너지 차이 가 작 을 수록 이 기 계 는 일 을 잘 한다.현재 2nk 개의 배터리 가 있 습 니 다.그들의 에 너 지 를 알 고 있 습 니 다.우 리 는 그것들 을 n 개의 기계 에 있 는 칩 에 놓 아서 모든 기계 의 에너지 차이 의 최대 치 를 최소 화해 야 합 니 다.
입력 형식
첫 번 째 줄,두 개의 정수,n 과 k.두 번 째 줄,2nk 의 정 수 는 모든 배터리 의 에 너 지 를 나타 낸다.
출력 형식
한 줄 한 줄 의 정 수 는 모든 기계 의 에너지 차이 의 최대 치가 가장 적은 지 를 나타 낸다.
샘플 입력
2 3 1 2 3 4 5 6 7 8 9 10 11 12
샘플 출력
1
샘플 입력
2 2 3 1 3 3 3 3 3 3
샘플 출력
2
데이터 규모 와 약정
　　2nk <= 10^6, 1 <= pi <= 10^9。
제목 대의:제목 번역 은 이미 충분히 간략 해 졌 으 니 더 이상 간소화 할 필요 가 없다.
사고방식 분석:2013 년 World Finals 에서 얻 기 어 려 운 물 문제 야!우선 기계 마다 2k 개의 배 터 리 를 분배 하면 에너지 의 차이 가 가장 작은 두 개의 배터리 의 차이 가 될 것 이다.마찬가지 로 우 리 는 모든 배터리 의 에 너 지 를 정렬 할 수 있다.모든 기계 의 에너지 차 이 는 반드시 정렬 한 후에 인접 한 두 개의 배터리 의 에너지 차이 이다.'최대 치가 가장 작다'는 생각 은 반드시 2 분 의 답 p 이다.만약 에 모든\(0\\le i\l n\)이 정렬 된 서열 의 앞\(2ki\)개 배터리 에 i 대 배터리 의 에너지 차이 가 p 보다 작다 면 이 p 는 요구 에 부합 한다.
알고리즘 흐름:
2 점 답 p 하고 욕심 내 서 판정 하면 돼 요.
참조 코드:

 1 //date 20140122

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <algorithm>

 5 

 6 using namespace std;

 7 

 8 const int maxnk = 1000006;

 9 

10 inline int getint()

11 {

12     int ans(0); char w = getchar();

13     while('0' > w || w > '9')w = getchar();

14     while('0' <= w && w <= '9')

15     {

16         ans = ans * 10 + w - '0';

17         w = getchar();

18     }

19     return ans;

20 }

21 

22 inline int max(int a, int b){return a > b ? a : b;}

23 inline int min(int a, int b){return a < b ? a : b;}

24 

25 int n, k, nk;

26 int chips[maxnk];

27 

28 inline bool check(int w)

29 {

30     for(int p = 1, q = 0; q < n; ++p)

31     {

32         if(p - 1 > q * 2 * k)return false;

33         if(chips[p + 1] - chips[p] <= w)++p, ++q;

34     }

35     return true;

36 }

37 

38 inline int solve(int l, int r)

39 {

40     int mid;

41     while(l < r)

42     {

43         mid = (l + r) >> 1;

44         if(check(mid))r = mid;

45         else l = mid + 1;;

46     }

47     return l;

48 }

49 

50 int main()

51 {

52     freopen("low.in", "r", stdin);

53     freopen("low.out", "w", stdout);

54     

55     while(scanf("%d%d", &n, &k) != EOF)

56     {

57         nk = 2 * n * k; int Max = 0;

58         for(int i = 1; i <= nk; ++i){chips[i] = getint(); Max  = max(Max, chips[i]);}

59         sort(chips + 1, chips + nk + 1);

60         int ans = solve(0, Max);

61         printf("%d
", ans);

62     }

63 

64     return 0;

65 }

주의 할 점 이 별로 없다.