贪心基础题相关 - “何妨吟啸且徐行”
2026-07-17 08:27:55
发布于：浙江
仅仅是自己的记录，并非写给他人看的教程。
—————————————————————————————————————————
配对贪心
P1094纪念品
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;
int a[N];
bool vis[N];
int main(){
int w,n;
cin>>w>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
int zh=1,fz=0;
for(int i=n;i>=1;i--){
if(vis[i])continue;
if(a[i]+a[zh]<=w){
vis[zh]=1;//
zh++;
fz++;
}else fz++;
}
cout<<fz;
return 0;
}
易错点：
vis[zh++]=1;
而不是
vis[++zh]=1;
即：得先标记zh，再将zh往后推一格。
证明与总结：
本题希望将序列中的元素分组，组中最多含有两个元素，和不超过。
不难想到将它们排序，努力将当前序列中最大的元素和最小的元素分在一组。
（我的总结）
现在来证明最大的元素和最小的元素分在一起一定是最优的。
是这样的：如果把最小的元素和别的元素分配在了一起，那么最大的元素就有可能无法分配到另一个元素导致单个元素成组。而”别的元素“本来却有可能可以和另外的元素组合在一起。
https://www.luogu.com.cn/problem/P1803
凌乱的yyy
这是一个比较典的贪心模板。
大概做法就是把所有的考试按照结束时间进行排序，然后遍历尽量多考点就好。
从直觉的角度来说，最早结束意味着时间消耗最小；从反例的角度来说，你会发现如果有一个很晚才结束的比赛排在最前面，那是没有比它晚结束的比赛比它更优秀的
那么从证明的角度呢？
这里介绍一个论证方法：交换论证
当此刻你有一个类似于排列的东西，你需要在它们中得到某些信息，求出最优解。此时你想了某种方法，将这个排列进行排序后（你认为）你能够得到正确答案。
如果你想证明，你就可以将这个排列中的某几个元素互换位置，证明通过交换，你不会得到一个更差的解
https://www.luogu.com.cn/problem/P3817
小A的糖果
这道题的题解区中，大家都觉得是道水题，但是我觉得这题不水。（其次就是，这道题目的题解去区有些能被hack掉）
先讲讲我的思路历程：
一.直觉
从一开始，我的思路很混乱，因为我觉得吃或或是一个相当麻烦的事情，选择哪个都会牵动后面的一系列连锁反应。
然后我去找deepseek，初步讨论出了（不知道为什么）先吃左边的糖是对的的结论。但是当时我并不认为这个结论是正确的。
所以后续我构造了一个反例： 它击破了“左边的糖先吃”这个假结论。
二.理解与证明
然后我去看题解，发现“先吃右边的糖才是正确的”，这让我想起了线段覆盖。因为它们好像都是“后者更重要”，但是这种感觉有点飘渺。所以我继续想它为什么是对的。
我觉得“先吃后者”是不难理解的。因为先吃后者，就是在为未来做准备：如果吃，那么它就能同时给予和便利。但如果吃，那么它只能对提供好处，因为是过去式。
现在看来（暂时）贪心要求只看未来，不看过去。
三.代码实现
代码实现的时候我遇到了很多问题，我先把代码贴出来。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//1.
const int N=1e5+5;
ll a[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
ll ans=0;
for(int i=1;i<=n-1;i++){
if(a[i]+a[i+1]<=m)continue;//2.
if(a[i]+a[i+1]-m>a[i+1]){//3.
ans+=(a[i+1]+a[i]-m);
a[i]-=((a[i+1]+a[i]-m)-a[i+1]);//4.
a[i+1]=0;
}else{
ans+=a[i]+a[i+1]-m;
a[i+1]-=a[i]+a[i+1]-m;
}
}
cout<<ans;
return 0;
}
1.要开long long
2.如果它们的和是符合要求的，就continue（不然未来它会舍得ans和a[i+1]减去一个负数）
3.判断a[i+1]的糖是否够减
这是一开始我没能意识到的。也就是说a[i]+a[i-1]-m是有可能大于a[i+1]的，而这种情况下，我们就不能让a[i+1]-=a[i]+a[i+1]-m，不然它会变成负数（而这不合法，题解去里的一小部分题解可以被这个hack掉）
4.在判断完a[i+1]的糖不够减之后，我们还得做出措施：即，如果a[i+1]的糖不够减，就减a[i]的糖
https://www.luogu.com.cn/problem/P5019
铺设道路
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int cnt=0;
for(int i=1;i<=n;i++){
while(a[i]){
a[i]--;
for(int j=i+1;j<=n;j++){
if(!a[j])break;
a[j]--;
}
cnt++;
}
}
cout<<cnt;
return 0;
}
这里空空如也
有帮助，赞一个