Educational Codeforces Round 77 (Rated for Div. 2) E. Tournament (DP)
程序员文章站
2022-06-04 09:57:36
...
题目:传送门
B站有详解点此跳转
这里只谈一谈,为什么直接贪心就可以了(这里其实是DP的思想)
首先不考虑贿赂的原因,那么这个满二叉树的每一条树链 自底向上能力值一定是单增的,越强的人能pk掉更多的人,所以可以把能力值高的人放在高轮次(便于后面贪心,当然放在前面被朋友pk掉也是可以的)。
对于-1前面的数字完全不必理会,因为朋友可以吊打他们。
那么我们就假定-1是第一个数字。对于朋友来说,第一轮选人pk,一定不可能选前1个(他自己),第二轮一定不可能选前3个(包括他自己),因为前3个人中的后两个人要么被朋友打败,要么被别人打败(能力值是排列),同理第三轮就是前7个人,第k轮就是前2^k-1个人不能选作朋友的pk对象。
我现取[2^k,n]最小值加入答案,删除该结点,然后继续向前拓展至[2 ^k-1,n] ,如过当前可取最小值的能力比以前取得的小,那么就正常取;否则也直接取,就相当于把以前取得向下调整,把当前的最小值插入到两个结点(之前已经保证能力值单增了)之间即可。
感觉不太清楚,但愿自己理解就行。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
const int N=1<<19+5;
const double inf=0x3f3f3f3f;
#define ls (i<<1)
#define rs (i<<1|1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define debug puts("...")
LL read()
{
LL x=0,t=1;
char ch=getchar();
while(!isdigit(ch)){ if(ch=='-')t=-1; ch=getchar(); }
while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); }
return x*t;
}
priority_queue<int,vector<int>,greater<int> > q;
LL a[N];
int main()
{
LL n=read();
for(int i=1;i<=n;i++) a[i]=read();
LL cnt;
for(cnt=1;cnt<=18&&1<<cnt!=n;cnt++);
LL ans=0;
for(int i=n;i;i--)
{
if(a[i]==-1) break;
q.push(a[i]);
if(i==1<<cnt)
{
cnt--;
ans+=q.top();
q.pop();
}
}
printf("%lld\n",ans);
return 0;
}
上一篇: 明末的一些奇葩“惊艳”景象!这样的明朝不垮才是奇迹!
下一篇: 男人吃甜食的危害,没想到竟然有这些
推荐阅读
-
Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing
-
Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
-
Educational Codeforces Round 60 (Rated for Div. 2) ----A - Best Subsegment(思维题)
-
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution(多颗树状数组+思维)
-
Educational Codeforces Round 85 (Rated for Div. 2) C. Circle of Monsters(前缀和 预处理 贪心)
-
Educational Codeforces Round 98 (Rated for Div. 2) A-E 题解
-
Educational Codeforces Round 93 (Rated for Div. 2) A. Bad Triangle
-
Educational Codeforces Round 93 (Rated for Div. 2) B - Substring Removal Game
-
Educational Codeforces Round 99 (Rated for Div. 2) C. Ping-pong
-
第十五次训练:Educational Codeforces Round 72 (Rated for Div. 2) && Codeforces Round #582 (Div. 3)