给定 n 个要求，在[ai,bi]的区间里必须要有 ci 个数。 求最少需要的数字个数。
构造前缀和 s[i] 。题目要求为 s[bi]−s[ai−1]>=ci ，马上联想到差分约束。 构造 ai−1−>bi 的边边权为 ci 。 因为要求答案最小，显然要刷最长路。 不要忽略题目中内在的条件， s[i+1]−s[i]<=1—>s[i]−s[i+1]>=−1,s[i+1]−s[i]>=0 。 因为有负权显然要用 spfa ，但是题目给出的条件告诉我们没有负环。
再来介绍一个贪心的想法。 先按 bi 排序，然后从后面往前面放数字，这样做也是对的， 考虑当前的区间，先用树状数组判断当前区间的数字个数是否已经满足，不满足就用并查集获取离 bi 最近的没有放置过数字的节点，修改这个节点的 fa ，并 add ,一直这么操作直到满足 ci 。
#include<cstdio> #include<cstring> #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; const int maxn=50005,maxm=150005; inline int _read(){ int num=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') num=num*10+ch-48,ch=getchar(); return num; } int m,n,dis[maxn],que[maxn],hed,til; int tot,nxt[maxm],son[maxm],w[maxm],lnk[maxn]; bool vis[maxn]; void add(int x,int y,int z){ nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;w[tot]=z; } int spfa(){ memset(dis,192,sizeof(dis)); hed=0;til=1;que[1]=0;vis[0]=1;dis[0]=0; while (hed!=til){ int x=que[hed=(hed+1)%maxn];vis[x]=0; for (int j=lnk[x];j;j=nxt[j]) if (dis[x]+w[j]>dis[son[j]]){ dis[son[j]]=dis[x]+w[j]; if (!vis[son[j]]){ que[til=(til+1)%maxn]=son[j]; vis[son[j]]=1; } } } return dis[n]; } int main(){ freopen("exam.in","r",stdin); freopen("exam.out","w",stdout); m=_read(); for (int i=1;i<=m;i++){ int x=_read(),y=_read(),z=_read(); add(x-1,y,z);n=max(n,y); } for (int i=1;i<=n;i++) add(i-1,i,0),add(i,i-1,-1); printf("%d\n",spfa()); return 0; }