題目鏈接：http://codeforces.com/contest/460/problem/C

題意：　ｎ盆花，澆ｋ次水， 每次可使花高度 +　１，　每次可澆相鄰的ｗ盆，ai 表示 i-th盆花 的高度　問(wèn)：當(dāng)澆完ｍ次后，最矮的一盆花最高可以使多少？

解題思路：　二分 +　掃描線，　由于高度最高１0ｅ９　＋ 10e5　，最小1， 然后在 這范圍內(nèi)二分搜索。?

? ? ? ? ? 這道題主要的還是check， ?怎樣檢查 澆完后是否能達(dá)到高度 h。 用樹狀數(shù)組或線段樹 自然可以， 復(fù)雜度：　建樹（nlogn ） +　點(diǎn)查詢（ｎlogn）。　不過(guò)還有種更小巧精悍的方法： 掃描線(n)。?

? ? ? ? ?例如在【0,2)，【1,3)范圍內(nèi)分別 +　１，　可以先ｆ[0] += 1, f[2] -= 1, f[1] += 1, f[3] -= 1,f: 1,1,-1,-1, 計(jì)算結(jié)果是，從左完后加： 1， 1 +１，1+1-1,1+1-1-1.?

1 /***Good Luck***/ 2 // 二分 +　掃描線 3 #define _CRT_SECURE_NO_WARNINGS 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <cstring> 8 #include <string> 9 #include <algorithm> 10 #include <stack> 11 #include <map> 12 #include <queue> 13 #include <vector> 14 #include <set> 15 #include <functional> 16 #include <cmath> 17 18 #define Zero(a) memset(a, 0, sizeof(a)) 19 #define Neg(a) memset(a, -1, sizeof(a)) 20 #define All(a) a.begin(), a.end() 21 #define PB push_back 22 #define inf 0x3f3f3f3f 23 #define inf2 0x7fffffffffffffff 24 #define ll long long 25 using namespace std; 26 //#pragma comment(linker, "/STACK:102400000,102400000") 27 const int maxn = 100005; 28 int arr[maxn]; 29 int f[maxn + maxn]; 30 int n, m, w; 31 32 bool check(int mnh) { 33 Zero(f); 34 int tmpm = m; 35 for (int i = 1; i <= n; ++i) {// 掃描線 36 f[i] = f[i] + f[i - 1]; 37 int d = max(0, mnh - arr[i] - f[i]); 38 tmpm -= d; 39 f[i] += d; 40 f[i + w] -= d; 41 if (tmpm < 0) return false; 42 } 43 return true; 44 } 45 46 void solve() { 47 int l = 0, r = 1000000000 + maxn; 48 int mid; 49 while (l < r) { 50 mid = (l + r + 1) >> 1; 51 if (check(mid)) { 52 l = mid ; 53 } else { 54 r = mid - 1; 55 } 56 } 57 cout << r << endl; 58 } 59 int main() { 60 //freopen("data.out", "w", stdout); 61 //freopen("data.in", "r", stdin); 62 cin.sync_with_stdio(false); 63 cin >> n >> m >> w; 64 for (int i = 1; i <= n; ++i) 65 cin >> arr[i]; 66 solve(); 67 return 0; 68 }

?

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

總結(jié)

以上是生活随笔為你收集整理的C. Present（二分 +　扫描线）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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