這道題讓最大值最小， 顯然是二分答案

當(dāng)題目求的是最大值最小， 最小值最大， 這個(gè)時(shí)候就要想到二分答案
為什么可以二分答案呢， 因?yàn)檫@個(gè)時(shí)候解是單調(diào)性的， 如果簡單粗暴一點(diǎn)
就全部枚舉一遍， 驗(yàn)證答案。但是因?yàn)榇鸢笣M足單調(diào)性， 可以用二分的方法
來”枚舉“， 復(fù)雜度可以從n降到logn

開始我自己寫了一個(gè)， 但是WA, 后來看了劉汝佳的代碼， 發(fā)現(xiàn)要注意三點(diǎn)

（1）這道題的和的最大值會爆int， 要用long long。

養(yǎng)成看到題目的時(shí)候計(jì)算最大值看會不會爆int的習(xí)慣（int最大大概是2乘10的9次方）

（2）輸出的時(shí)候，因?yàn)槭乔懊娴淖有蛄械暮捅M量小， 所以我自己寫的時(shí)候想到了從后
往前盡量取（貪心）來輸出， 但是沒有考慮到分成固定要分成k個(gè)。 所以要專門用一個(gè)remain

來控制分成子序列的個(gè)數(shù)， 不然子序列會分少。

（3） 二分開始時(shí)候的左端點(diǎn)一定要設(shè)為元素最大值， 我一開始有想到， 但是覺得好像
對答案沒有什么影響， 就懶得去求最大值， 就直接設(shè)為0， 然后就WA了。
事實(shí)上， 在判斷這個(gè)答案是否符合的時(shí)候（我的程序中的judge函數(shù)），這個(gè)key值
根本就小于元素的時(shí)候， 是可以通過的， 這個(gè)錯(cuò)誤是非常難發(fā)現(xiàn)的， 所以要提前
處理， 也就是在一開始的時(shí)候最小的可能的答案就設(shè)為元素最大值
順便提一下， 我的程序中l(wèi)--， 是因?yàn)槲业亩值膶懛ㄊ沁@么寫的。

#include<cstdio> #include<cstring> #include<algorithm> #define REP(i, a, b) for(int i = (a); i < (b); i++) using namespace std;typedef long long ll; const int MAXN = 512; int a[MAXN], board[MAXN], n, k;bool judge(ll key) {ll num = 1, sum = 0;REP(i, 0, n){if(sum + a[i] <= key) sum += a[i];else {num++; sum = a[i];if(num > k) return false;}}return true; }void print(ll key) {memset(board, 0, sizeof(board));ll sum = 0, remain = k;for(int i = n - 1; i >= 0; i--){if(sum + a[i] > key || i + 1 < remain) sum = a[i], board[i+1] = 1, remain--;else sum += a[i];}printf("%d", a[0]);REP(i, 1, n){if(board[i]) printf(" /");printf(" %d", a[i]); }puts(""); }int main() {int T;scanf("%d", &T);while(T--){ll l = 0, r = 0;scanf("%d%d", &n, &k);REP(i, 0, n) scanf("%d", &a[i]), r += a[i], l = max(l, (ll)a[i]);l--;while(l + 1 < r){ll mid = (l + r) / 2;if(judge(mid)) r = mid;else l = mid;}print(r);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/sugewud/p/9819591.html

總結(jié)

以上是生活随笔為你收集整理的紫书 例题8-10 UVa 714 （二分答案）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。