|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <stack> using namespace std; #define MAXN 100005 int hana[MAXN]; int prevGrow[MAXN];//this is a sum int fetchPrevGrow(int curr,int w){ if(curr > w){ return (prevGrow[curr-1] - prevGrow[curr-w]); }else{ return prevGrow[curr-1]; } } bool ok(int n,int m,int w,int target){ memset(prevGrow, 0, sizeof(prevGrow)); int res = 0; for (int i = 1; i <= n; i++) { int growed = fetchPrevGrow(i, w); int toGrow = target - growed - hana[i]; if (toGrow < 0) toGrow = 0; prevGrow[i] = prevGrow[i-1] + toGrow; res += toGrow; if (res > m) { return false; } } return true; } int main(){ int n = 0,m = 0,w = 0; while (cin >> n >> m >> w) { memset(hana, 0, sizeof(hana)); int maxhana = 0; for (int i = 1; i <= n; i++) { scanf(" %d",&hana[i]); maxhana = max(maxhana,hana[i]); } int low = 0,high = maxhana+m,mid = (low+high)/2,ans = 0; while (low <= high) { mid = (low+high)/2; if (ok(n, m, w, mid)) { ans = max(ans, mid); low = mid + 1; }else{ high = mid - 1; } } cout << ans << endl; } return 0; } |
二分答案求解，这种求最小值的最大值，或者可以转化成求最小值的最大值的问题都可以通过二分答案，回代验证的方法求解。
这个题要注意在ok那个函数中res会被加爆int，如果把判定推出的if写进for里就可以避免加爆还能剪枝加速，要么就用long long也是可以的。
注意在回代检验的过程中，使用了前缀和来快速提取当前节点已经在先前被浇了多少次水。
January 20, 2015
= = 多加点说明呗 最好能把每个函数的目的打一下 不好看懂啊混蛋//我就是来试一下乱打电子邮件和姓名能不能评论的
January 20, 2015
我尽量，实在不行代码里面写题解