最近练了一些贪心的题目，虽然思想都是局部最优的思想，但是落实到每一题上其实会有细微的差别，复盘一下题目加深印象。
P2240 【深基12.例1】部分背包问题
这一题按照性价比排序就可以了，性价比最高的排在最前面。为了避免除法带来的问题，我们比较两个点的性价比用叉乘的方式来比较
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
bool cmp(pii a,pii b)
{
return a.second*b.first>a.first*b.second;
}
void solve()
{
int n,m;
cin>>n>>m;
vector<pii>ve(n+1);
for(int i=0;i<n;i++)
{
cin>>ve[i].first>>ve[i].second;
}
sort(ve.begin(),ve.end(),cmp);
int sum=0;
double ans=0;
for(int i=0;i<n;i++)
{
int last=0;
last=sum;
if(sum+ve[i].first<m){
sum+=ve[i].first;
ans+=ve[i].second;
}
else{
ans+=(m-last)*(1.0*ve[i].second/ve[i].first);
break;
}
}
printf("%.2lf",ans);
}
signed main()
{
solve();
}
P1223 排队接水
求平均接水的最短时间，那么我们需要在人尽量多的时候先排尽量小的取水时间，从小到大排序计算总时间然后除以n就行
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
bool cmp(pii a,pii b)
{
if(a.second!=b.second) return a.second<b.second;
else return a.first<b.first;
}
void solve()
{
int n;
cin>>n;
vector<pii>ve(n+1);
for(int i=1;i<=n;i++)
{
ve[i].first=i;
cin>>ve[i].second;
}
sort(ve.begin()+1,ve.end(),cmp);
int sum=0;
for(int i=1;i<=n;i++)
{
sum+=(n-i)*ve[i].second;
cout<<ve[i].first<<" ";
}
cout<<endl;
printf("%.2lf",1.0*sum/n);
}
signed main()
{
solve();
}
P1803 凌乱的yyy / 线段覆盖
经典的不重复的线段区间题，我们只需要把每个点按第二个值从小到大的排序，然后看看下一个点的头有没有大于等于上一个点的尾即可
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
bool cmp(pii a,pii b)
{
return a.second<b.second;
}
void solve()
{
int n;
cin>>n;
vector<pii>ve(n+1);
for(int i=1;i<=n;i++)
{
cin>>ve[i].first>>ve[i].second;
}
sort(ve.begin()+1,ve.end(),cmp);
int end=ve[1].second;
int ans=1;
for(int i=1;i<=n;i++){
if(ve[i].first>=end){
end=ve[i].second;
ans++;
}
}
cout<<ans;
}
signed main()
{
solve();
}
P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
这一题使用一个优先队列，把每次对头的前两个拿出来，然后加起来再放进去，把队列取完就是答案了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
void solve()
{
priority_queue<int,vector<int>,greater<int> >q;
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
q.push(x);
}
int ans=0;
while(q.size()>=2)
{
int a=q.top();
q.pop();
int b=q.top();
q.pop();
q.push(a+b);
ans+=a+b;
}
cout<<ans;
}
signed main()
{
solve();
}
P3817 小A的糖果
每次输入的时候就检查一下和上一个加起来有没有超过题意限制，有就减掉那部分就可以了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
void solve()
{
int n,m,sum=0;
cin>>n>>m;
int last=0;
while(n--)
{
int x;
cin>>x;
if(last+x>m){
sum+=last+x-m;
last=m-last;
}
else last=x;
//cout<<last<<endl;
}
cout<<sum;
}
signed main()
{
solve();
}
P1106 删数问题
遍历每一个数如果当前这个数大于后面这个数就把它给删除掉，但是要注意特判10和删除前导零，在这题我们还可以学一个技巧，就是不要前导0我们不是把它删掉，而是记录第一个不是0的下标再开始输出
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
void solve()
{
string s;
int n;
cin>>s;
cin>>n;
int l=s.size();
while(n--)
{
for(int i=0;i<=l;i++)//可以删除2222这种是因为可以遍历到第l位 而第l位位'/0'其ASCII码为0
{
if(s[i]>s[i+1]) {
for(int j=i;j<=l;j++) s[j]=s[j+1];
l--;
break;//删完以后变成了一个新的数字，跳出循环，继续查找和删除
}
}
}
int st=0,i=0;//st是开始输出字符串的位置，用来跳过前导0；省的删除
//st<l-1是为了防止10啥也不输出
while(s[i]=='0'&&st<l-1)
{
st++;
i++;
}
for(int i=st;i<l;i++) cout<<s[i];
}
signed main()
{
solve();
}
P1478 陶陶摘苹果（升级版）
把高度小于a+b的按照消耗的力气小从小到大排序，放进优先队列即可，考虑一下特殊情况当n=0或s=0时，ans=0
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
void solve()
{
int n,s,a,b;
priority_queue<pii,vector<pii>,greater<pii> >q;
cin>>n>>s;
//特判 当n=0或s=0时，ans=0；
cin>>a>>b;
if(n==0) {
cout<<"0";
return;
}
while(n--)
{
int x,y;
cin>>x>>y;
if(x<=(a+b))
{
q.push({y,x});
}
}
int ans=0,sum=0;
while(1)
{
auto g=q.top();
q.pop();
// cout<<g.first<<" "<<g.second<<endl;
s-=g.first;
if(s<0) break;
ans++;
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
solve();
return 0;
}
P5019 [NOIP2018 提高组] 铺设道路
这一题的做法比较抽象，需要图形上的理解，
我们可以想象一下俄罗斯方块的消除情况，就是最底下一层可以全部消掉，当4这四层全部消掉了以后会剩下一个U字形，再删掉会剩下一个l型，很奇妙的是就是只要算出每两个相邻数的差分，当差分为正，结果加上这个值就可以，但是我还没想明白为啥
点击查看代码
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n,last,sum=0;
cin>>n;
cin>>last;
int a1=last;
for(int i=2;i<=n;i++)
{
int x;
cin>>x;
int temp=x-last;
if(temp>0) sum+=temp;
last=x;
}
cout<<sum+a1;
}
int main()
{
solve();
}
P1208 [USACO1.3] 混合牛奶 Mixing Milk
还是按照单价从小到大排序来做跟上面有一题是一样的
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define int long long
char c[105][105];
int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
int a[25],b[25][25];
bool cmp(pii a,pii b)
{
if(a.first!=b.first) return a.first<b.first;
else return a.second<b.second;
}
void solve()
{
int n,m;
cin>>n>>m;
vector<pii>ve(m+1);
for(int i=1;i<=m;i++)
{
cin>>ve[i].first>>ve[i].second;
}
sort(ve.begin()+1,ve.end(),cmp);
int sum=0,last=0,ans=0;
for(int i=1;i<=m;i++)
{
if(sum+ve[i].second<n){
sum+=ve[i].second;
ans+=ve[i].first*ve[i].second;
}
else {
ans+=(n-sum)*ve[i].first;
break;
}
}
cout<<ans;
}
signed main()
{
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
P1094 [NOIP2007 普及组] 纪念品分组
这题其实就是大小配对一下而已，还是排序一下然后取头和尾即可，用vector来存，然后开一个l 和 r ，l=1，r=m；用来取头和取尾，这个思路也是可以学习的
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define int long long
char c[105][105];
int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
int a[25],b[25][25];
void solve()
{
int n,m;
cin>>n;
cin>>m;
vector<int>ve(m+1);
for(int i=1;i<=m;i++) cin>>ve[i];
sort(ve.begin()+1,ve.end(),greater<int>());
int l=1,r=m,ans=0;
while(l<=r)
{
if(ve[l]+ve[r]<=n){
ans++;
l++;
r--;
}
else {
ans++;//超出范围让他自己一组
l++;
}
}
cout<<ans;
}
signed main()
{
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}