??????? 把可能的進行二分判斷，判斷的時候盡量向右取，一直取到不能去為止，這樣才有可能成功分割。

判斷是否可以把up作為最大值的代碼：

bool judge(LL up){if(up < Big) return false; //Big是數組中最大值，如果up小于最大值是不可能成功劃分的LL sum = 0;int cnt = 0;for(int i = 0; i < n; ){sum = 0;while(i < n){sum += a[i];if(sum <= up) ++i;else break;}++cnt;}if(cnt <= k) return true; //成功劃分return false; }

值得注意的是，最后得到最小的最大值時應該如何劃分，題目要求前面的盡量小，那么就從后面盡可能多的劃分，但是不能只滿足小于等于up，也要考慮到組成k個序列，不能讓某些序列為空。

AC代碼：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int maxn = 500 + 5; int a[maxn], vis[maxn]; int Big = -1; //Biggest number int n,k; //Divid n numbers to k squencesbool judge(LL up){if(up < Big) return false;LL sum = 0;int cnt = 0;for(int i = 0; i < n; ){sum = 0;while(i < n){sum += a[i];if(sum <= up) ++i;else break;}++cnt;}if(cnt <= k) return true;return false; }LL Binary_Search(LL x, LL y){ //[x,y]while(x < y){LL mid = x + (y - x) / 2;bool ok = judge(mid);if(ok) y = mid;else x = mid + 1;}return y; }int main(){int T;scanf("%d", &T);while(T--) {memset(vis, 0, sizeof(vis));LL sum = 0;Big = -1;scanf("%d%d",&n,&k);for(int i = 0; i < n; ++i){scanf("%d",&a[i]);sum += a[i];Big = max(Big, a[i]);}LL up = Binary_Search(1, sum);LL div;int cnt = 0;for( int i = n-1; i >= 0;){div = 0;while(div <= up && i >= 0 && i + 1 >= k - cnt){div += a[i];if(div <= up) --i;}++cnt;if(i >= 0) vis[i] = 1;}//print the answerfor(int i = 0; i < n; ++i){if(i == n-1) printf("%d\n", a[i]);else printf("%d ", a[i]);if(vis[i]) printf("/ ");}}return 0; }
如有不當之處歡迎指出！

轉載于:https://www.cnblogs.com/flyawayl/p/8305470.html

總結

以上是生活随笔為你收集整理的UVA-714 二分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。