1、B站视频链接:A25 贪心算法 P1223 排队接水_哔哩哔哩_bilibili
题目链接:排队接水 - 洛谷
#include <bits/stdc++.h>
using namespace std;
struct node{int t,id;//接水时间,编号bool operator<(node &b){return t<b.t;}
}a[1010];int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i].t,a[i].id=i;}sort(a+1,a+1+n);for(int i=1;i<=n;i++){cout<<a[i].id<<" ";}puts("");double time=0;for(int i=1;i<=n-1;i++){//因为最后一个人不需要等待所有n-1 time+=a[i].t*(n-i);}printf("%.2lf",time/n);return 0;
}
2、B站视频链接:A26 贪心算法 P1190 [NOIP2010 普及组] 接水问题_哔哩哔哩_bilibili
题目链接:[NOIP2010 普及组] 接水问题 - 洛谷
#include <bits/stdc++.h>
using namespace std;
int n,m,w[10010];//w是接水量
int s[110];//每个龙头的出水量int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&w[i]);for(int i=1,t;i<=n;i++){t=1;//假设1号水龙头排水量最少//找到排水量最小的水龙头for(int j=2;j<=m;j++){if(s[t]>s[j])t=j;} s[t]+=w[i];}int maxn=0;for(int i=1;i<=m;i++)maxn=max(maxn,s[i]);printf("%d\n",maxn); return 0;
}
小根堆实现版
#include <bits/stdc++.h>
using namespace std;
int n,m,w[10010];//w是接水量
priority_queue<int,vector<int>,greater<int>>s;
//小根堆维护最小值
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&w[i]);for(int i=1;i<=m;i++)s.push(0);for(int i=1;i<=n;i++){int t=s.top();s.pop();//维护最小出水量 s.push(t+w[i]);}for(int i=1;i<m;i++){//把小的全部弹出,剩下的即为最大 s.pop();}printf("%d\n",s.top());return 0;
}
题目链接:[USACO05MAR] Yogurt factory 机器工厂 - 洛谷
#include <bits/stdc++.h>
using namespace std;
//上次的单价花费+s与当前单价花费做比较,
//哪个花费更少,就取哪个。
int main(){int n,s,c,y,last;//last表示上次的生产花费 long long ans=0;cin>>n>>s;for(int i=1;i<=n;i++){cin>>c>>y; if(i==1)last=c;//没有last取自己为当前 else last=min(last+s,c);ans+=last*y;}cout<<ans<<endl;return 0;
}