当前位置：首页 > news >正文

算法竞赛备考冲刺必刷题（C++） | 洛谷 P10934 西瓜种植

news 2026/7/17 8:56:59

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P10934 西瓜种植 - 洛谷

【题目描述】

笨笨种了一块西瓜地，但这块西瓜地的种植范围是一条直线的……

笨笨在一番研究过后，得出了m mm个结论，这m mm个结论可以使他收获的西瓜最多。

笨笨的结论是这样的：

从西瓜地b bb处到e ee处至少要种植t tt个西瓜，这个范围的收获就可以最大化。

笨笨不想那么辛苦，所以他想种植的西瓜尽量少，而又满足每一个所得的结论。

【输入】

第一行两个数n nn,m mm（0 < n ≤ 5000 0<n \le 50000<n≤5000，0 ≤ m ≤ 3000 0 \le m\le 30000≤m≤3000），表示笨笨的西瓜地长n nn，笨笨得出m mm个结论。

接下来m mm行表示笨笨的m mm个结论，每行三个数b bb,e ee,t tt（1 ≤ b ≤ e ≤ n 1 \le b\le e\le n1≤b≤e≤n，0 ≤ t ≤ e − b + 1 0 \le t\le e-b+10≤t≤e−b+1）。

【输出】

输出笨笨最少需种植多少西瓜。

【输入样例】

9 4 1 4 2 4 6 2 8 9 2 3 5 2

【输出样例】

【算法标签】

《洛谷 P10934 西瓜种植》 #贪心# #差分约束#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=5005,M=N*3;// 最大顶点数和边数inth[N],e[M],w[M],ne[M],idx;// 链式前向星存储图intdist[N];// 最长距离数组boolst[N];// 标记顶点是否在队列中intn,m;// n: 范围[0,n], m: 区间约束数量/** * 添加有向边 * @param a 起点 * @param b 终点 * @param c 权重 */voidadd(inta,intb,intc){e[idx]=b;// 边指向的顶点w[idx]=c;// 边的权重ne[idx]=h[a];// 指向原链表头h[a]=idx++;// 更新头指针}/** * SPFA算法求最长路径 * 从顶点0开始，计算到所有顶点的最长路径 */voidspfa(){// 初始化距离为负无穷memset(dist,-0x3f,sizeof(dist));memset(st,0,sizeof(st));queue<int>q;// SPFA队列q.push(0);// 起点入队st[0]=true;// 标记在队列中dist[0]=0;// 起点距离为0while(!q.empty()){intt=q.front();// 取出队首q.pop();st[t]=false;// 标记不在队列中// 遍历t的所有邻接边for(inti=h[t];i!=-1;i=ne[i]){intj=e[i];// 邻接顶点// 松弛操作：求最长路径if(dist[j]<dist[t]+w[i]){dist[j]=dist[t]+w[i];// 更新最长距离// 如果j不在队列中，入队if(!st[j]){q.push(j);st[j]=true;}}}}}intmain(){// 输入n和区间约束数量mcin>>n>>m;// 初始化邻接表memset(h,-1,sizeof(h));// 添加基础约束边// 顶点编号0~n，共n+1个顶点for(inti=1;i<=n;i++){// 约束1: S_i - S_{i-1} ≤ 1// 即: S_{i-1} - S_i ≥ -1// 建边: i → i-1，权重-1add(i,i-1,-1);// 约束2: S_i ≥ S_{i-1}// 即: S_i - S_{i-1} ≥ 0// 建边: i-1 → i，权重0add(i-1,i,0);}// 添加区间约束while(m--){intb,e,t;cin>>b>>e>>t;// 约束: S_e - S_{b-1} ≥ t// 即: S_e ≥ S_{b-1} + t// 建边: b-1 → e，权重tadd(b-1,e,t);}// 执行SPFA算法求最长路径spfa();// 输出从0到n的最长路径长度cout<<dist[n]<<endl;return0;}