本文主要是介绍D4代码AC集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
贪心问题解决的步骤:
(局部贪心能导致全局贪心)
1.确定贪心策略
2.验证贪心策略是否正确
排队接水
#include<bits/stdc++.h>
using namespace std;
int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1,j=n;int cnt=0;while(i<=j){if(a[i]+a[j]<=w){cnt++;i++;j--;}else if(a[i]+a[j]>w){cnt++;j--;}}cout<<cnt;return 0;
}
独木舟
#include<bits/stdc++.h>
using namespace std;
struct node{int bh,sj;
}a[220];
int n;
bool cmp(node x,node y){if(x.sj==y.sj){return x.bh<y.bh;}else{return x.sj<y.sj;}
}
int main(){cin>>n; double sum=0;for(int i=1;i<=n;i++){cin>>a[i].sj;a[i].bh=i;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){cout<<a[i].bh<<" ";}for(int i=1;i<=n;i++){sum+=(n-i+1)*a[i].sj;}cout<<endl;printf("%.2lf",sum/n);return 0;
}
删数问题
#include<bits/stdc++.h>
using namespace std;
int main(){int s;string n;cin>>n;cin>>s;while(s--){int flag=0;for(int i=0;i<n.size()-1;i++){if(n[i]>n[i+1]){n.erase(i,1);flag=1;break;}}if(flag==0){n.erase(n.size()-1,1);}}int f1=0;for(int i=0;i<=n.size()-1;i++){if(n[i]!='0'){f1=1;}if(f1==1){cout<<n[i];}}if(f1==0){cout<<0;}return 0;
}
最小新整数
#include<bits/stdc++.h>
using namespace std;
int main(){int s,t;string n;cin>>t;while(t--){cin>>n;cin>>s;int l=0;while(s--){int flag=0; l=n.size();for(int i=0;i<l-1;i++){if(n[i]>n[i+1]){n.erase(i,1);flag=1;break;}}if(flag==0){n.erase(l-1,1);}}int f1=0;l=n.size();for(int i=0;i<=l-1;i++){if(n[i]!='0'){f1=1;}if(f1==1){cout<<n[i];}}cout<<endl;}return 0;
}
拦截导弹问题
#include<bits/stdc++.h>
using namespace std;
int main(){int cnt=0,n=1;int a[1100],b[1100],flag=0;while(cin>>a[n]){n++;}n--;int ans=1;//共ans个系统b[1]=a[1];for(int i=2;i<=n;i++){flag=0;for(int j=1;j<=ans;j++){if(b[j]>=a[i]){//能拦截b[j]=a[i];flag=1;break;}}if(flag==0){b[++ans]=a[i];}}cout<<ans;return 0;
}
这篇关于D4代码AC集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!