当前位置: 首页 > >

AtCoder NIKKEI Programming Contest 2019 C. Different Strokes (贪心)

发布时间:

题目链接: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,排序贪心取即可。


?



1 #include
2 using namespace std;
3 #define ll long long
4 #define ull unsigned long long
5 #define mst(a,b) memset((a),(b),sizeof(a))
6 #define mp(a,b) make_pair(a,b)
7 #define pi acos(-1)
8 #define pii pair
9 #define pb push_back
10 #define lowbit(x) ((x)&(-x))
11 const int INF = 0x3f3f3f3f;
12 const double eps = 1e-6;
13 const int maxn = 1e5 + 10;
14 const int maxm = 1e6 + 10;
15 const ll mod = 998244353;
16
17 int a[maxn];
18
19 int main() {
20 #ifdef local
21 freopen("data.txt", "r", stdin);
22 // freopen("data.txt", "w", stdout);
23 #endif
24 int n;
25 scanf("%d",&n);
26 ll ans = 0;
27 for(int i = 0; i < n; i++) {
28 int x,y;
29 scanf("%d%d",&x,&y);
30 a[i] = x + y;
31 ans -= y;
32 }
33 sort(a, a + n);
34 int cur = 1;
35 for(int i = n - 1; i >= 0; i--) {
36 if(cur) ans += a[i];
37 cur ^= 1;
38 }
39 printf("%lld",ans);
40 return 0;
41 }

?



转载于:https://www.cnblogs.com/scaulok/p/10328214.html



友情链接: