★贪心问题解决的步骤：
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;
}
