UVa 714 抄书（贪心+二分）

题意：把一个包含m个正整数的序列划分成k个非空的连续子序列，使得每个正整数恰好属于一个序列。设第i个序列的各数之和为S（i），你的任务是让所有S（i）的最大值尽量小。

思路：“最大值尽量小”问题。

区间的范围肯定是所有数中最大的一个至所有数之和，我们可以使用二分法来确定这样的一个值x，x尽量小并且每个区间都不大它。

题目要求的是前面的区间尽量小，那我们就需要贪心一下，从右边的数开始分配区间。需要注意的是，如果当前剩下来的待分配区间的数正好等于还要分配的组数，那么前面的几个数每个数都为一个区间。

 #include<cstring>

 #include<string>

 #include<iostream>

 using namespace std;

 const int maxn =  + ;

 int n, m;

 long long _max,left,right,_min;

 int a[maxn];

 int ans[];

 bool judge(long long mid)  //判断能否每组都小于等于mid

 {

     long long sum = ;

     int t = ;

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

     {

         if (sum + a[i] > mid)

         {

             sum = a[i];

             t++;

             if (t > m)  return false;   //需要分的组数大于了给定的m组，返回false

         }

         else

             sum += a[i];

     }

     return true;

 }

 void solve()

 {

     memset(ans, , sizeof(ans));

     ::left = _min, ::right = _max;

     while (::left <= ::right)

     {

         long long mid = (::left + ::right) / ;

         if (judge(mid))

         {

             ::right = mid - ;

         }

         else ::left = mid + ;

     }

     long long sum = ;

     int count = ;

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

     {

         if (sum + a[i] > ::left)

         {

             sum = a[i];

             ans[i] = ;

             count++;

         }

         else

             sum += a[i];

         if (m - count == i + )   //如果剩下来的值数量正好等于要划分的组数，那么一个数为一组

         {

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

                 ans[j] = ;

             break;

         }

     }

     for (int i = ; i < n - ; i++)

     {

         cout << a[i] << " ";

         if (ans[i])  cout << "/ ";

     }

     cout << a[n - ] << endl;

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     int t;

     cin >> t;

     while (t--)

     {

         cin >> n >> m;

         _min = ;

         _max = ;

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

         {

             cin >> a[i];

             if (_min < a[i])  _min = a[i];

             _max += a[i];

         }

         solve();

     }

     return ;

 }

巴特西

UVa 714 抄书（贪心+二分）

最新文章

热门文章