Description
You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn. Write a program that: reads the number of intervals, their end points and integers c1, ..., cn from the standard input, computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n, writes the answer to the standard output.Input
The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.Sample Input
5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1Sample Output
6这个题就是让你找出一个总的序列s包括如：
3 4 5 6 7 的序列中s中至少有三个
8-10中s至少有3个
6-8中s至少有1个
1-3中s至少有1个
10 11中至少有1个
问你s最少有多少个能满足上述的情况。
这题我们就用差分约束的方法，可以令题目更简单
这里我们用d数组来存（意义就是如：d[6]代表0-5中s最少包含几个）
那么条件就会满足
0<=d[i+1]-d[i]<=1;
d[v+1]-d[u]>=dist;
我们求得是满足所有的条件那么就要找“最大路径”也就是所有的条件都要“<=”
我们将上面的公式变形就会得到：
d[i+1]-d[i]<=1;
d[i]-d[i+1]<=0;
d[u]-d[v+1]<=-dist;
然后我们就可以用SPFA算法求得了。
代码如下：
#include <cstring> #include <cstdio> #include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; const int N = 50010; const int INF = 0x3f3f3f3f; struct node { int dist, to, next; }E[3*N]; int head[N], d[N], n, tot; bool vis[N]; void AddEdge(int u, int v, int dist) { E[tot].to = v; E[tot].dist = dist; E[tot].next = head[u]; head[u] = tot++; } void SPFA(int Min, int Max) { int i; for ( i = Min;i <= Max; i++ ) { d[i] = INF; vis[i] = 0; } queue<int> q; q.push(Max); d[Max] = 0; vis[Max] = 1; while ( !q.empty() ) { int u = q.front(); q.pop(); vis[u] = false; for ( i = head[u]; i != -1; i = E[i].next) { int v = E[i].to; if (d[v] > d[u] + E[i].dist) { d[v] = d[u] + E[i].dist; if (!vis[v]) { vis[v] = true; q.push(v); } } } } } void solve() { memset( head, -1, sizeof(head) ); tot = 0; int Min = INF, Max = -INF; int u, v, i, h; for ( i = 0;i < n; i++ ) { scanf ( "%d %d %d", &u, &v, &h ); Min = min(Min, u); Max = max(Max, v+1); AddEdge(v+1, u, -h); } for ( i = 0;i < Max; i++ ) { AddEdge(i, i+1, 1); AddEdge(i+1, i, 0); } SPFA(Min, Max); printf ( "%d\n", d[Max] - d[Min] ); } int main() { while ( ~scanf ( "%d", &n ) ) { solve(); } return 0; } 代码菜鸟，如有错误，请多包涵！！！如有帮助记得支持我一下，谢谢！！！
