c multimap_emacs python c-c c-c i 不好使_a=b=c,a=b==c c语言(12)

棋盘

 1 //二分答案、单调队列优化DP
 2 #include<bits/stdc++.h>
 3 #define MAXN 500002
 4 using namespace std;
 5 inline int read(){
 6     int a = 0;
 7     bool f = 0;
 8     char c = getchar();
 9     while(!isdigit(c)){
10         if(c == '-')    f = 1;
11         c = getchar();
12     }
13     while(isdigit(c))    a += (a << 3) + a + (c ^ '0') , c = getchar();
14     return f ? -a : a;
15 }
16 inline int max(int a , int b){return a > b ? a : b;}
17 int num[MAXN][2] , maxN[MAXN] , N , d , K;
18 bool vis[MAXN];
19 bool check(int mid){
20     deque < int > q;
21     int ALLmax = 0 , r = 0;
22     for(int i = 1 ; i <= N && ALLmax < K ; i++){
23         while(num[i][0] - num[r][0] > d + mid)    r++;
24         while(num[i][0] - num[r][0] >= max(d - mid , 1) && num[i][0] - num[r][0] <= d + mid){
25             if(vis[r]){
26                 while(!q.empty() && maxN[q.back()] <= maxN[r])
27                     q.pop_back();
28                 q.push_back(r);
29             }
30             r++;
31         }
32          while(!q.empty() && num[i][0] - num[q.front()][0] > d + mid)
33              q.pop_front();
34          if(!q.empty()){
35              ALLmax = max(ALLmax , maxN[i] = maxN[q.front()] + num[i][1]);
36              vis[i] = 1;
37         }
38         else    vis[i] = 0;
39     }
40     return ALLmax >= K;
41 }
42 int main(){
43     N = read();    d = read();    K = read();
44     for(int i = 1 ; i <= N ; i++){
45         num[i][0] = read();
46         num[i][1] = read(); 
47     }
48     vis[0] = 1;
49     int l = 0 , r = 1e9 + 1;
50     while(l < r){
51         int mid = l + r >> 1;
52         if(check(mid))    r = mid;
53         else    l = mid + 1;
54     }
55     if(r == 1e9 + 1)    cout << -1;
56     else    cout << l;
57     return 0;
58 }

*跳房子

posted @ 2018-11-08 15:09CJOIer_Itst 阅读(...) 评论(...) 编辑

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-124192-12.html