GESP4级考试语法知识（贪心算法（二））

排队接水2代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct people
{int num;int time;
};
people s[1001];
int n,r,a[1001];
double sum,ave;
bool cmp(people x,people y)
{return x.time<y.time;
}
int main()
{cin>>n>>r;int min=0,j=0;for(int i=1;i<=n;i++){cin>>s[i].time;s[i].num=i;}sort(s+1,s+n+1,cmp);for(int i=1;i<=n;i++){j++;if(j==r+1) j=1;a[j]+=s[i].time;min+=a[j];}cout<<min<<endl;return 0;
}

均分纸牌代码：

#include<iostream>
using namespace std;
int n,a[110];
int sum,ave,ans;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}ave=sum/n;for(int i=1;i<=n-1;i++){if(a[i]==ave) continue;int t=ave-a[i];a[i+1]-=t;ans++;}cout<<ans<<endl;return 0;
}

删数问题代码1：

#include<iostream>
using namespace std;
string s;
int n,k,mark=0,temp,flag=0;
int find_min(int l,int r)
{char minc=s[l];mark=l+1;for(int i=mark;i<=r;i++){if(s[i]<minc){minc=s[i];mark=i+1;}}return minc-'0';
}
int main()
{cin>>s>>k;n=s.length();for(int i=0;i<n-k;i++){temp=find_min(mark,k+i);if(flag==0&&temp==0) continue;flag=1;cout<<temp;}if(flag==0) cout<<0;return 0;
}

删数问题代码2：

#include<iostream>
using namespace std;
int s,len;
string n;
int main()
{cin>>n;cin>>s;len=n.length();for(int i=1;i<=s;i++)   //一共要删除 s个字符{for(int j=0;j<s+i;j++) //从串首开始找if(n[j]>n[j+1])    //找到符合条件的字符{for(int k=j;k<len-1;k++)n[k]=n[k+1];break;}len--;}int j=0;int m=len;int flag=0;for(int i=0;i<len;i++){if(n[i]=='0'&&flag==0) continue;flag=1;cout<<n[i];}if(flag==0) cout<<'0'<<endl;return 0;
}