【题目大意】：让你从[1-∞] 选择数字，需要满足要求A，给定多组a,b,c，要求在[a,b]中必须有c个被选中，问，最少选多少个数字即可满足要求。
【解题思路】：所有的要求都必须满足，即满足【最难满足】的要求。不妨设ans[i]表示，在i之前（[1,i-1]）最少选中几个。则要求可以变成 ans[b+1]-ans[a] ≥ c。
不妨想象成，从a点到b+1点有一条单向边，权为c，必须满足上面式子，即要求最长的c【最难满足】需要走，即转化为最长路问题。
另外这个转化还有一个隐藏条件.
即i到i+1点不能出现负边（ans[i+1]>ans[i]）
i+1最多比i多一个数字（ans[i+1]-ans[i]≤1）
将上面的式子整理下来
ans[b+1]≥ans[a]+c
ans[i+1]≥a[i]+0
ans[i]≥ans[i+1]-1
这样写，很明显应该建立
a---(c)--->b+1
i---(0)--->i+1
i+1---(-1)---i
最大路求得ans[max(b+1)]即可
初始化为ans[min(a)] = 0
1 #include "iostream" 2 #include "cstdio" 3 #include "vector" 4 #include "algorithm" 5 #include "queue" 6 #include "cstring" 7 using namespace std; 8 struct edge 9 { 10 int a, v; 11 edge(int aa = 0, int vv = 0): a(aa), v(vv) {} 12 }; 13 bool v [50004]; 14 int d [50004]; 15 vector E[50004]; 16 int main() 17 { 18 int N; 19 int Min = 500005, Max = -1; 20 memset(d, -1, sizeof(d)); 21 memset(v, false, sizeof(v)); 22 cin >> N; 23 while (N--) 24 { 25 int a, b, c; 26 scanf("%d%d%d", &a, &b, &c); 27 Min = min(Min, a); 28 Max = max(Max, b + 1); 29 edge A(b + 1, c); 30 E[a].push_back(A); 31 } 32 for (int i = Min; i <= Max; i++) 33 { 34 edge A(i + 1, 0); 35 E[i].push_back(A); 36 edge B(i, -1); 37 E[i + 1].push_back(B); 38 } 39 queue<</span>int> q; 40 d[Min] = 0; 41 q.push(Min); 42 v[Min] = true; 43 while (!q.empty()) 44 { 45 int now = q.front(); 46 q.pop(); 47 v[now] = false; 48 for (int i = 0 ; i < E[now].size(); i++) 49 { 50 edge e = E[now][i]; 51 if (d[e.a] < d[now] + e.v) 52 { 53 d[e.a] = d[now] + e.v; 54 if (!v[e.a]) 55 { 56 q.push(e.a); 57 v[e.a] = true; 58 } 59 } 60 } 61 } 62 cout << d[Max] << endl; 63 }