当前位置:   article > 正文

Codeforces Round #508 (Div. 2) C Gambling(贪心)_codeforces round #508 (div. 2)c题

codeforces round #508 (div. 2)c题

题目大意:两个人玩游戏,每个人两种操作,从自己那里拿一个数(是自己的得分),或者删除对手那里的一个数

两个人都想最大化自己的得分,并最小化对方的得分,求A-B,得分的差值

思路:博弈,如果对手的最大的数比自己最大的数还大,就删除对方的数,否则就拿自己那里的最大的数

比赛的时候傻逼了,没开ll一直wa,误以为int的范围是ll的范围,ORZ,赛后改ll过了

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. #include<iostream>
  5. #include<math.h>
  6. #include<queue>
  7. #include<string>
  8. #include<vector>
  9. #include<map>
  10. const int inf = 0x3f3f3f3f;
  11. using namespace std;
  12. const int N = 1e6+9;
  13. const int mod = 1e9+7;
  14. #define ll long long
  15. int n,k;
  16. int vis[29];
  17. int a[N],b[N];
  18. int main()
  19. {
  20. //freopen("in.txt","r",stdin);
  21. scanf("%d",&n);
  22. for(int i = 1; i<=n; i++) scanf("%d",&a[i]);
  23. for(int i = 1; i<=n; i++) scanf("%d",&b[i]);
  24. sort(a+1,a+n+1);
  25. sort(b+1,b+n+1);
  26. int t = 2*n;
  27. int k = 1;
  28. int i =n, j = n;
  29. ll ansa = 0,ansb = 0;
  30. while(t--)
  31. {
  32. if(k&1)//A
  33. {
  34. if(a[i]>b[j]){
  35. ansa+=a[i];
  36. i--;
  37. }
  38. else {
  39. j--;
  40. }
  41. }
  42. else{//B
  43. if(a[i]>=b[j])
  44. {
  45. i--;
  46. }
  47. else if(a[i]<b[j]){
  48. ansb+=b[j];
  49. j--;
  50. }
  51. }
  52. k++;
  53. }
  54. printf("%I64d\n",ansa-ansb);
  55. return 0;
  56. }

 

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号