AtCoder NIKKEI Programming Contest 2019 C. Different Strokes （贪心）

时间：2021-10-28 15:11:02

题目链接：https://nikkei2019-qual.contest.atcoder.jp/tasks/nikkei2019_qual_C

题意：给出 n 种食物，Takahashi 吃下获得 ai 快乐值，Aoki 吃下获得 bi 快乐值，两人轮流吃，他们的目标是最大化自己获得的快乐值减去她人获得的快乐值吗，问最后该值是多少。

题解：易知 Takahashi 要最大化答案而 Aoki 要最小化答案，考虑全部食物由 Aoki 吃下，则ans = -（b1 + b2 + .... + bn），但 Takahashi 会吃下一些食物，则这时候 Takahashi 吃下食物获得的快乐值为 ai + bi，排序贪心取即可。

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 #define lowbit(x) ((x)&(-x))

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int maxn = 1e5 + ;

 const int maxm = 1e6 + ;

 const ll mod =  ;

 int a[maxn];

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     int n;

     scanf("%d",&n);

     ll ans = ;

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

         int x,y;

         scanf("%d%d",&x,&y);

         a[i] = x + y;

         ans -= y;

     }

     sort(a, a + n);

     int cur = ;

     for(int i = n - ; i >= ; i--) {

         if(cur) ans += a[i];

         cur ^= ;

     }

     printf("%lld",ans);

     return ;

 }

相关文章