3463. 【NOIP2013模拟联考5】军训(training) (Standard IO)
Time Limits: 2000 ms Memory Limits: 262144 KB Detailed Limits
Goto ProblemSet做法:我们可以二分最大的女友指数最小时为多少,可以设f[i]表示i 开头的班级的欠扁值之和
优化见代码。
代码如下:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <cstdio> 2 #include <iostream> 3 #include <string> 4 #include <cstring> 5 #define LL long long 6 #define N 20007 7 using namespace std; 8 LL n, limit, h[N], g[N], sum[N], num[N], z[N], ans, mid, f[N]; 9 int next[N]; 10 11 LL get(int t) 12 { 13 LL tl = t, tr = n; 14 while (tl < tr) 15 { 16 LL mi = (tl + tr) / 2; 17 if (sum[mi] - sum[t - 1] >= mid) tr = mi; 18 else tl = mi + 1; 19 } 20 return tl; 21 } 22 23 bool check() 24 { 25 memset(f, 0x7f7f7f7f, sizeof(f)); 26 f[1] = 0; 27 for (int i = 1; i <= n; i++) 28 { 29 int k = get(i); 30 int x = i; 31 int ma = h[i]; 32 if (sum[k] - sum[i - 1] > mid) k--; 33 while (x <= k) 34 { 35 f[x] = min(f[x], f[i] + ma); 36 ma = h[x]; 37 x = next[x]; 38 } 39 f[k + 1] = min(f[k + 1], f[i] + ma); 40 } 41 if (f[n + 1] <= limit) return 1; 42 return 0; 43 } 44 45 int main() 46 { 47 scanf("%lld%lld", &n, &limit); 48 for (int i = 1; i <= n; i++) 49 { 50 scanf("%lld%lld", &h[i], &g[i]); 51 sum[i] = sum[i - 1] + g[i]; 52 } 53 int tail = 1; 54 z[1] = 1e9 + 7; 55 num[1] = n + 1; 56 for (int i = n; i >= 1; i--) 57 { 58 while (h[i] >= z[tail]) tail--; 59 next[i] = num[tail]; 60 tail++; 61 z[tail] = h[i]; 62 num[tail] = i; 63 } 64 ans = sum[n]; 65 LL tl = 1, tr = ans; 66 while (tl < tr) 67 { 68 mid = (tl + tr) / 2; 69 if (check()) 70 { 71 if (mid < ans) ans = mid; 72 tr = mid; 73 } 74 else tl = mid + 1; 75 } 76 printf("%lld", tl); 77 }