CodeForces - 730A 贪心+模拟
2024-09-14 04:20:48
贪心策略:
1、只有一个最大值,选着第二大的一起参加比赛减分。
2、有奇数个最大值,选择三个进行比赛。
3、偶数个最大值,选择两个进行比赛。
为什么不把最大值全部选择?
因为最多只能选五个,有可能选择完五个只剩下一个最大值,那么就会进行贪心策略1,会出错。
AC代码:
#include<cstdio> #include<set> using namespace std; const int maxn=1e4+1; char ans[maxn][101]; int cnt=0,n; struct node{ int ind; int val; node(){} node(int i,int v):ind(i),val(v){} bool operator < (const node &p)const{ return val>p.val; } }score[105]; multiset<node>ss; typedef multiset<node>::iterator iter; inline int counter(){ //相同最大值的个数 int key=(ss.begin())->val; int cntt=0; for(iter c=ss.begin();c!=ss.end();++c){ if(c->val==key) ++cntt; else break; } return cntt; } inline void deal(int k,int *a){ for(int i=0;i<k;++i){ if(score[a[i]].val>0) score[a[i]].val-=1; ss.insert(score[a[i]]); } for(int i=0;i<n;++i){ int ok=0; for(int j=0;j<k;++j) if(a[j]==i) {ok=1;break;} if(ok) ans[cnt][i]='1'; else ans[cnt][i]='0'; } cnt++; } //模拟 void solve(){ int cnt=counter(); if(cnt==n) return; int k=0,a[5]; if(cnt==1||cnt%2==0) { iter c=ss.begin(); a[k++]=c->ind; ss.erase(c); c=ss.begin(); a[k++]=c->ind; ss.erase(c); deal(k,a); } else if(cnt>1&&cnt&1){ iter c=ss.begin(); a[k++]=c->ind; ss.erase(c); c=ss.begin(); a[k++]=c->ind; ss.erase(c); c=ss.begin(); a[k++]=c->ind; ss.erase(c); deal(k,a); } solve(); } int main(){ scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%d",&score[i].val); score[i].ind=i; ss.insert(score[i]); } solve(); printf("%d\n",(ss.begin())->val); printf("%d\n",cnt); for(int i=0;i<cnt;++i) printf("%s\n",ans[i]); return 0; }
昨晚我又想了下,其实还有一种直观贪心:
1、只有一个最大值,选择最大和第二大进行比赛。
2、如果有6个最大值,选择4个比赛。不能选5个,因为一定要把所有最大值同时处理掉。
3、如果最大值大于6,选择5个比赛。
4、其他大于1小于等于5的情况,就全部选择参加比赛
AC代码:
#include<cstdio> #include<set> using namespace std; const int maxn=1e4+1; char ans[maxn][101]; int cnt=0,n; struct node{ int ind; int val; node(){} node(int i,int v):ind(i),val(v){} bool operator < (const node &p)const{ return val>p.val; } }score[105]; multiset<node>ss; typedef multiset<node>::iterator iter; inline int counter(){ //相同最大值的个数 int key=(ss.begin())->val; int cntt=0; for(iter c=ss.begin();c!=ss.end();++c){ if(c->val==key) ++cntt; else break; } return cntt; } inline void deal(int k,int *a){ for(int i=0;i<k;++i){ if(score[a[i]].val>0) score[a[i]].val-=1; ss.insert(score[a[i]]); } for(int i=0;i<n;++i){ int ok=0; for(int j=0;j<k;++j) if(a[j]==i) {ok=1;break;} if(ok) ans[cnt][i]='1'; else ans[cnt][i]='0'; } cnt++; } //模拟 void solve(){ int cntt=counter(); if(cntt==n) return; int k=0,a[5]; if(cntt==6) cntt=4; else if(cntt>=7) cntt=5; else if(cntt==1) cntt=2; for(int i=0;i<cntt;++i){ iter c=ss.begin(); a[k++]=c->ind; ss.erase(c); } deal(k,a); solve(); } int main(){ scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%d",&score[i].val); score[i].ind=i; ss.insert(score[i]); } solve(); printf("%d\n",(ss.begin())->val); printf("%d\n",cnt); for(int i=0;i<cnt;++i) printf("%s\n",ans[i]); return 0; }
如有不当之处欢迎指出!
最新文章
- IIS部署遇到的一些问题
- 2016/11/16 周三 <;使用LocalStore记住用户密码方法示例>;
- bootstrap-fileinput简单完整列子
- Web 软件测试 Checklist 应用系列,第 1 部分: 数据输入
- TCP/IP协议原理与应用笔记17:IP编址(重点)
- 练习题之CyclicBarrier与CountDownLatch
- java csv - 读写及其操作.
- WPF Binding值转换器ValueConverter使用简介(二)-IMultiValueConverter
- 关于Unix时间戳
- window nfs 服务端配置安装
- yii2 Nav::widget() 和 Menu::widget()
- 老李分享:持续集成学好jenkins之内置命令
- Ubuntu MariaDB PhpMyAdmin
- Java五种基本的Annotation,提高程序的可读性
- springboot+mockito 异常解决方案
- Hexo NexT 博客本地搭建指南
- B2C B2B C2C O2O模式的介绍
- tp3.2分页
- Jenkins+Maven+SVN+Nexus自动化部署代码实例
- idea如何导入一个maven项目