WF2013Low Power芯片

Description

有n个机器，每个机器有2个芯片，每个芯片可以放k个电池。

每个芯片能量是k个电池的能量的最小值。

两个芯片的能量之差越小，这个机器就工作的越好。

现在有2nk个电池，已知它们的能量，我们要把它们放在n个机器上的芯片上，

使得所有机器的能量之差的最大值最小。

Input

第一行，两个正整数，n和k。

第二行，2nk个整数，表示每个电池的能量。

Output

一行一个整数，表示所有机器的能量之差的最大值最小是多少。

Solution

二分所有机器的能量之差的最大值，然后找到符合这一数值的芯片，标记起来，模拟一遍就好了。

Code

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int a[],n,k,num;

 bool b[];

 bool check(int x)

 {

     int p=,t=;

     for (int i=; i<=num; i++) b[i]=false;

     for (int i=; i<=num; i++)

       if ((b[i-]==false)&&(a[i]-a[i-]<=x))//标记能量最小值的芯片

       {

           t++;

         b[i]=true; b[i-]=true;

         if (t==n) break;

       }

     if (t<n) return false;

     t=;

     for (int i=num; i>=; i--)

       if (b[i])

       {

          t++; //t表示当前找到几块能量最小值芯片

          if (p<t*(k-)) return false;//检验多余的芯片够不够放入机器而不影响最小值

          if (t==n*) break;

       }

         else p++;//p表示有几块多余芯片

     return true;

 }

 int main()

 {

   cin>>n>>k;

   num=*n*k;

   for (int i=;i<=num;i++)

     cin>>a[i];

   sort(a+,a+num+);

   int left=,right=a[num],mid,ans=;

   while (left<=right)

   {

      mid=(left+right)/;

      if (check(mid)) {ans=mid; right=mid-;}

        else left=mid+;

   }

   cout<<ans<<endl;

   return ;

 }

Source

http://www.lydsy.com/JudgeOnline/problem.php?id=3969

秒客网