CodeForces - 730A 贪心+模拟

   贪心策略：

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("%dn",(ss.begin())->val);
printf("%dn",cnt);
for(int i=0;i<cnt;++i)
printf("%sn",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("%dn",(ss.begin())->val);
printf("%dn",cnt);
for(int i=0;i<cnt;++i)
printf("%sn",ans[i]);
return 0;
}

如有不当之处欢迎指出！