【Mail.Ru Cup 2018 Round 3 C. Pick Heroes 】模拟+交互题

C. Pick Heroes

题意

有两个势力，给你2*n个英雄，每个英雄有战斗力，两方轮流选择英雄
有m对英雄有捆绑关系，对于每对捆绑的英雄，若某一个被其中一方选择
则下个回合另一方必须选择捆绑的另一个英雄
要求尽量使所选英雄总战斗力值最大
如果最开始输入1，则表示你先选择，否则对手先选择

做法

首先如果我们先手，我们肯定先选完所有捆绑英雄中最战斗力大的那一个，
之后剩下的英雄中不断选择战斗力最高的就可以
如果我们后手，对手选择捆绑英雄的情况我们只能跟着选
否则我们直接转守为攻，选择完所有捆绑英雄，
之后再每次可以选的时候直接选剩下的英雄里战斗力最大的

代码

#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 1e4+5;
int vis2[maxn];
int vis[maxn];
int l[maxn],r[maxn];
struct data
{
    int id,num;
}a[maxn];
bool cmp(const data &a,const data &b)
{
    return a.num<b.num;
}
int xx[maxn];
int main()
{
    int n,m,x;scanf("%d%d",&n,&m);for(int i=1;i<=2*n;i++){
    scanf("%d",&a[i].num);a[i].id=i;xx[i]=a[i].num;}sort(a+1,a+1+2*n,cmp);for(int i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]);int op;scanf("%d",&op);if(op==1){
    int pos=1;for(int i=1;i<=n;i++){
    if(pos<=m){
    if(xx[l[pos]]>xx[r[pos]]){
    vis[l[pos]]=1;printf("%d\n",l[pos]);fflush(stdout);}else{
    vis[r[pos]]=1;printf("%d\n",r[pos]);fflush(stdout);}pos++;}else{
    for(int j=2*n;j>=1;j--){
    if(!vis[a[j].id]){
    vis[a[j].id]=1;printf("%d\n",a[j].id);fflush(stdout);break;}}}scanf("%d",&x);vis[x]=1;}}else{
    for(int i=1;i<=n;i++){
    scanf("%d",&x);vis[x]=1;int flag=0;for(int j=1;j<=m;j++){
    if(vis2[j]) continue;if(l[j]==x){
    vis2[j]=1;flag=1;vis[r[j]]=1;printf("%d\n",r[j]);fflush(stdout);break;}else if(r[j]==x){
    vis2[j]=1;flag=1;vis[l[j]]=1;printf("%d\n",l[j]);fflush(stdout);break;}}if(flag==0){
    int ff=0;for(int j=1;j<=m;j++){
    if(!vis2[j]){
    ff=1;vis2[j]=1;if(xx[l[j]]>xx[r[j]]){
    vis[l[j]]=1;printf("%d\n",l[j]);fflush(stdout);}else{
    vis[r[j]]=1;printf("%d\n",r[j]);fflush(stdout);}break;}}if(ff==0){
    for(int j=2*n;j>=1;j--){
    if(!vis[a[j].id]){
    vis[a[j].id]=1;printf("%d\n",a[j].id);fflush(stdout);break;}}}}}}return 0;
}