-----------------------------------------------------------

 

 

 https://www.nowcoder.com/acm/contest/13/F

 

给定m个区间，其中l-r之间至少有k个点，求最少的点的个数。

 

一眼看上去是差分约束，但是范围太大只能通过60%，正解是贪心，按照右端点p排序，每次贪心往最右端放，可以保证最优

 

1 #include "iostream" 2 #include 
     
       3 using namespace std; 4  5  6 const int maxm = 1000009; 7 const int maxn = 500009; 8 #define bt(x) x&(-x) 9 10 struct Node {11     int l, r, z;12 }T[maxm];13 14 bool cmp(Node a, Node b){15     if(a.r == b.r) return a.l < b.l;16     return a.r < b.r;17 }18 19 int sum[maxn], n, m;20 21 void add(int x){22     while(x <= n+1){23         sum[x] += 1;24         x += bt(x);25     }26 }27 28 int query(int x){29     int cnt = 0;30     while(x){31         cnt += sum[x];32         x -= bt(x);33     }34     return cnt;35 }36 37 bool vis[maxn];38 39 int main(){40     scanf("%d%d", &n, &m);41     for(int i = 0; i < m; ++i){42         scanf("%d%d%d", &T[i].l, &T[i].r, &T[i].z);43     }44     sort(T, T+m, cmp);45     for(int i = 0; i < m; ++i){46         int x = query(T[i].r+1) - query(T[i].l);47         if(x < T[i].z){48             int xx = T[i].z - x;49             for(int j = T[i].r+1; xx; --j){50                 if(!vis[j]){51                     vis[j] = true;52                     xx --;53                     add(j);54                 }55             }56         }57     }58     printf("%d\n", query(n+1));59     return 0;60 }
     

 

 ----------------------------------------------------------------

 

 

只有不断学习才能进步！