每日一题 day18 打卡
Analysis
贪心
假如小A先选最大的[5,4],虽然电脑必须选一个破坏， 我们可以理解为5和4都属于小A的，假如后面未被破坏的最大值无论是和5相关还是和4相关，必然还是属于小A先手。 写个极限情况，假设6个武将的最大值序列依次为[1,2],[3,4]，[5,6]，电脑肯定要破坏掉这三种选择。后面第四个值无论是哪个组合，小A必然能通过先手在第二次或第三次先选到这两个武将，也就是说选择的总次数不会超过n/2。 因此，只要将武将组合值排序，由大到小依次选择下去，一定会触发小A胜利条件。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define int long long 7 #define maxn 500*(500-1)/2+10 8 using namespace std; 9 inline int read() 10 { 11 int x=0; 12 bool f=1; 13 char c=getchar(); 14 for(; !isdigit(c); c=getchar()) if(c=='-') f=0; 15 for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0'; 16 if(f) return x; 17 return 0-x; 18 } 19 inline void write(int x) 20 { 21 if(x<0){putchar('-');x=-x;} 22 if(x>9)write(x/10); 23 putchar(x%10+'0'); 24 } 25 int n,cnt; 26 struct node 27 { 28 int x,y,val; 29 }inn[maxn]; 30 bool book[maxn]; 31 inline bool cmp(node x,node y) 32 { 33 return x.val>y.val; 34 } 35 signed main() 36 { 37 n=read(); 38 for(int i=1;i<=n-1;i++) 39 for(int j=i+1;j<=n;j++) 40 { 41 cnt++; 42 inn[cnt].val=read(); 43 inn[cnt].x=i; 44 inn[cnt].y=j; 45 } 46 sort(inn+1,inn+cnt+1,cmp); 47 for(int i=1;i<=cnt;i++) 48 { 49 if(book[inn[i].x]==0&&book[inn[i].y]==0) 50 { 51 book[inn[i].x]=1; 52 book[inn[i].y]=1; 53 } 54 else 55 { 56 write(1); 57 printf("\n"); 58 write(inn[i].val); 59 return 0; 60 } 61 } 62 write(0); 63 return 0; 64 }
请各位大佬斧正