洛谷 P1199 三国游戏 题解

每日一题 day18 打卡

Analysis

贪心

假如小A先选最大的[5,4],虽然电脑必须选一个破坏， 我们可以理解为5和4都属于小A的，假如后面未被破坏的最大值无论是和5相关还是和4相关，必然还是属于小A先手。 写个极限情况，假设6个武将的最大值序列依次为[1,2],[3,4]，[5,6]，电脑肯定要破坏掉这三种选择。后面第四个值无论是哪个组合，小A必然能通过先手在第二次或第三次先选到这两个武将，也就是说选择的总次数不会超过n/2。 因此，只要将武将组合值排序，由大到小依次选择下去，一定会触发小A胜利条件。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define int long long

 #define maxn 500*(500-1)/2+10

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int n,cnt;

 struct node

 {

     int x,y,val;

 }inn[maxn];

 bool book[maxn];

 inline bool cmp(node x,node y)

 {

     return x.val>y.val;

 }

 signed main()

 {

     n=read();

     for(int i=;i<=n-;i++)

         for(int j=i+;j<=n;j++)

         {

             cnt++;

             inn[cnt].val=read();

             inn[cnt].x=i;

             inn[cnt].y=j;

         }

     sort(inn+,inn+cnt+,cmp);

     for(int i=;i<=cnt;i++)

     {

         if(book[inn[i].x]==&&book[inn[i].y]==)

         {

             book[inn[i].x]=;

             book[inn[i].y]=;

         }

         else

         {

             write();

             printf("\n");

             write(inn[i].val);

             return ;

         }

     }

     write();

     return ;

 } 

请各位大佬斧正