1 条题解
-
8
所以这道题的标签是不是得加上个博弈论那就是想最优策略呗~ 如果轮到小X选择,那么肯定选择所有叠的顶端的最大数,并且,如果那张牌底下有一张比它大的牌,那么这一叠牌是不会选的。假设全选前小X与小Y相差a,如果小X选择了那一叠(假设上面为x,下面为y且y>x且x为),那么加上这个数x,那么轮到小Y选择,肯定会选择y,那么差会缩小y-x,这是小X不愿看到的,所以这一叠是不会选择的。小Y选择也是同理
但是可能会有a[i]相同的情况,如果是小X选择a[i],那么会优先考虑b[i]小的,这样可能会使小Y加的更少
#include <bits/stdc++.h> #define ll long long #define int long long #define cin read() using namespace std; inline int read(){ char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48,ch=getchar();} return x*f; } inline void write(int x) { if(x<0) x=-x,putchar('-'); if(x<10) putchar(x+'0'); else write(x/10),putchar(x%10+'0'); } struct node { int x, y; bool operator <(const node &a)const{ return x == a.x ? y > a.y : x < a.x; } }a; ll n,num,sum1,sum2,ans=-1e9; priority_queue<node> q; main() { n=cin; for (int i = 1; i <= n; i++){ a.x=cin; a.y=cin; q.push(a); } while(q.size()){ node t = q.top(); q.pop(); if(t.y > t.x) continue; if(num & 1){ sum2 += t.x; ans = max(ans, sum1 - sum2); }else{ sum1 += t.x; } if(t.y != -1) t.x = t.y, t.y = -1, q.push(t); num++; } ans = max(ans, sum1 - sum2); write(ans); return 0; }
点个赞呗
Orz
- 1
信息
- ID
- 523
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- 递交数
- 45
- 已通过
- 33
- 上传者