★贪心问题解决的步骤:
1.确定贪心策略
2.验证贪心策略是否正确
贪心策略不唯一,但整体思路相似
排队接水
题目描述
有n个人在一个水龙头前排队接水,假如每个人接水的时间为Ti,请编程找出这n个人排队的一种顺序(若有多种顺序则编号小的在前), 使得n个人的平均时间花费最小。
输入描述
输入文件共两行,第一行为n;第二行分别表示第 1 个人到第n个人每人的接水时间T1,T2,…,Tn,每 个数据之间有 1 个空格。n<200.
输出描述
输出文件有两行,第一行为一种排队顺序,即1到n的一种排列;第二行为这种排列方案下的平均等 待时间(输出结果精确到小数点后两位)。
样例
输入
10 56 12 1 99 1000 234 33 55 99 812
输出
3 2 7 8 1 4 9 6 10 5 532.00
代码
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
int n;
double t[205];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>t[i];}int minn=0x3f3f3f3f,k;double sum=0.0;for(int i=1;i<=n;i++){minn=0x3f3f3f3f; for(int j=1;j<=n;j++){if(t[j]!=0){if(minn>t[j]){minn=t[j];k=j;}}}cout<<k<<" ";sum+=t[k]*(n-i+1);t[k]=0;}cout<<"\n";printf("%.2lf",1.0*sum/n);return 0;
}
独木舟
题目描述
我们计划搞一次独木舟旅游活动。独木舟可以在港口租到,并且它们之间是没有区别的。一条独木舟上最多只能乘坐两个人,且乘客的总重量不能超过独木舟的最大承载量。我们想要尽可能的减少我们在这次活动中的花销,所以要找出可以安置所有旅客的最少的独木舟的条数。
任务: 请写一个程序: 读入独木舟的最大承载量,旅客的数目和每位旅客的重量; 根据给出的规则,计算要安置所有旅客所必须最少的独木舟的条数; 把结果输出
输入描述
在第一行包括一个整数w,80 <= w <= 200,为一条独木舟的最大承载量。
文件的第二行为一个整数n,1 <= n <= 30000,表示旅客的数目。
以下的n行中每行包含一个[5..w]中的整数,表示所对应旅客的重量。
输出描述
你应该在第一行输出一个整数——所需要的最少独木舟的数目。
样例
输入
100 9 90 20 20 30 50 60 70 80 90
输出
6
提示
80 <= w <= 200
1 <= n <= 30000
代码
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
int n,w,a[30005];
int main(){cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int cnt=0;int x=1,y=n;while(x<=y){if(a[x]+a[y]<=w){cnt++;y--;x++;}else{y--;cnt++;}}cout<<cnt;return 0;
}
删数问题
题目描述
输入一个高精度的正整数n,去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s,寻找一种方案使得剩下的数字组成的新数最小。
输出新的正整数。(n不超过240位)
输入数据均不需判错
输入描述
n
s
输出描述
最后剩下的最小数。
样例
输入
175438 4
输出
13
代码
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
string n;
int s;
int main(){cin>>n>>s;int len=n.size()-2;while(s--){bool f=0;for(int i=0;i<=len;i++){if(n[i+1]<n[i]){//比下一个大 n.erase(i,1);f=1;break;}} if(!f){n.erase(len+1,1);}}bool f=0; for(int i=0;i<=n.size()-1;i++){if(n[i]!='0'){f=1;}if(f==1){//遇到过非0的数,全输出 cout<<n[i];}}if(f==0){cout<<0;} return 0;
}
最小新整数
题目描述
给定一个十进制正整数n(0<n<1000000000),每个数位上数字均不为0。n的位数为m。
现在从m位中删除k位(0<k<m)
求生成的新整数最小为多少?
例如: n=9128456,k=2,则生成的新整数最小为12456。
输入描述
第一行t, 表示有t组数据;
接下来t行,每一行表示一组测试数据,每组测试数据包含两个数字n,k。
输出描述
t行,每行一个数字,表示从n中删除k位后得到的最小整数。如果能删空,输出空行
样例
输入
2 9128456 2 1444 3
输出
12456 1
代码
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
string n;
int s;
int t;
int main(){cin>>t;while(t--){cin>>n>>s;while(s--){bool f=0;int len=n.size()-2;for(int i=0;i<=len;i++){if(n[i+1]<n[i]){//比下一个大 n.erase(i,1);f=1;break;}} if(!f){n.erase(len+1,1);}}bool f=0; int len=n.size();for(int i=0;i<=len-1;i++){if(n[i]!='0'){f=1;}if(f==1){//遇到过非0的数,全输出 cout<<n[i];}}cout<<endl;}return 0;
}
拦截导弹问题
题目描述
某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统,但是这种拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度不大于30000的正整数)。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。
输入描述
n颗依次飞来的高度(1≤n≤1000)。
输出描述
要拦截所有导弹最小配备的系统数k。
样例
输入
389 207 155 300 299 170 158 65
输出
2
提示
输入:导弹高度: 4 3 2
输出:导弹拦截系统k=1
代码
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
int a[1005],b[1005];
int main(){int n=1;while(cin>>a[n]){n++;}n--;int ans=1;int f=0;b[1]=a[1];for(int i=2;i<=n;i++){f=0;for(int j=1;j<=ans;j++){if(b[j]>=a[i]){b[j]=a[i];f=1;break;}}if(f==0){b[++ans]=a[i];}}cout<<ans;return 0;
}