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

样例输出

样例输入

2 2
3 1 3 3 3 3 3 3

样例输出

数据规模和约定

　　2nk <= 10^6, 1 <= pi <= 10^9。

题目大意：题目翻译已经足够简略了，不需要再简化了。。

思路分析：2013年World Finals难得的水题啊！首先每台机器分配2k个电池，那它的能量之差最小值一定是最小的两个电池的差。同样的，我们可以对所有电池的能量进行排序，每一台机器的能量之差一定是排序后相邻两节电池的能量之差。看到“最大值最小”的想法一定是二分答案p，如果对于所有\(0\le i \le n\)在排序后的序列中的前\(2Ki\)个电池中，都存在i对电池的能量之差小于等于p，则这个p是合要求的

算法流程：

二分答案p然后贪心判定即可

参考代码：

 //date 20140122

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxnk = ;

 inline int getint()

 {

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

     while('' > w || w > '')w = getchar();

     while('' <= w && w <= '')

     {

         ans = ans *  + w - '';

         w = getchar();

     }

     return ans;

 }

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

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

 int n, k, nk;

 int chips[maxnk];

 inline bool check(int w)

 {

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

     {

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

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

     }

     return true;

 }

 inline int solve(int l, int r)

 {

     int mid;

     while(l < r)

     {

         mid = (l + r) >> ;

         if(check(mid))r = mid;

         else l = mid + ;;

     }

     return l;

 }

 int main()

 {

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

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

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

     {

         nk =  * n * k; int Max = ;

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

         sort(chips + , chips + nk + );

         int ans = solve(, Max);

         printf("%d\n", ans);

     }

     return ;

 }

没什么需要注意的地方。。

巴特西

ACM - ICPC World Finals 2013 F Low Power

最新文章

热门文章