在这里就介绍两种做法
题意：
自己看看吧，很明显的意思，就是求前i个人最少有多少个话筒。
解法1：差分约束
设\(dis[i]\)表示前\(i\)个人最少有多少个话筒
根据题目意思每个人都只能有一个话筒 所以 \(dis[i[+1>=dis[i+1] dis[i+1]>=dis[i]\)
\(a_i\)到\(b_i\)至少有\(c_i\)个 所以 \(dis[a_i-1]+c_i>=dis[b_i]\)
转换一下跑一遍最长路即可。
CODE:
#include#include #include #include #include #include #define N 30010#define M 5050#define INF 214748364using namespace std;struct edge { int to; int from; int data;}e[N * 2 + 1];int head[N],cnt;int dis[N],m,n;bool vis[N];queue q;inline void add_edge(int x,int y,int z) { e[++cnt].from = y; e[cnt].data = z; e[cnt].to = head[x]; head[x] = cnt;}void spfa() { for(int i = 1 ; i <= n ; i++) dis[i] = -19260817; dis[1] = 0; q.push(1); vis[1] = true; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u] ; i ; i = e[i].to) { int v = e[i].from; if(dis[u] + e[i].data > dis[v]) { dis[v] = dis[u] + e[i].data; if(!vis[v]) { q.push(v); vis[v] = true; } } } }}int main() { //n = read(), m = read(); scanf("%d%d",&n,&m); while(m--) { //int l = read(), r = read(), k = read(); int u , v , w; scanf("%d%d%d",&u,&v,&w); add_edge(u - 1 , v , w); } for(int i = 1 ; i <= n ; i++) { add_edge(i - 1 , i , 0); add_edge(i , i - 1 , -1); } spfa(); printf("%d\n", dis[n]); return 0;}
啥，你不想写SPFA。不过没关系，我们还有另一种做法。
解法2：贪心
我们可以先按所有声部的右端点排序，再进行从后到前的顺序选取拿话筒的人。很显然，如果我们从后往前选取，就会尽量满足后面人的需求，这样就能达到最小值。
CODE:
#include#include #include #include using namespace std;const int N = 31000;struct node { int a; int b; int c;}e[N];int m,n,ans;int vis[N];inline bool cmp(node x,node y) { if(x.b != y.b) return x.b < y.b; return x.a < y.a;}void init() { scanf("%d%d",&n,&m); for(int i = 1 ; i <= m ; i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);}void work() { sort(e+1 , e + m + 1 , cmp); for(int i = 1 ; i <= m ; i++) { int cnt = 0; for(int j = e[i].b ; j >= e[i].a ; j--) { if(vis[j]) cnt++; } if(cnt > e[i].c) continue; else { for(int j = e[i].b ; (j >= e[i].b - e[i].c + 1 && cnt < e[i].c) ; j--) { if(!vis[j]) vis[j] = 1 , cnt++ , ans++; } } } printf("%d\n",ans);}int main() { init(); work(); return 0;}