比赛评分

Description

Lj最近参加一个选秀比赛，有N个评委参加了这次评分，N是奇数。评委编号为1到N。每位评委给Lj打的分数是一个

整数，评委i(1 ≦ i ≦ N)的打分为Di。这次采用了一种创新的方法计算最后得分，计算规则是：最初N位评委排

成一排，检查队伍排头的3位评委的评分，去掉一个最高分和一个最低分，剩下的一个评委移动到队伍最后，反复

执行以上操作，直到队伍中的评委只剩一位，那么这个评委的打分就是Lj的最后得分。由于有的评委年纪比较大了

，不记得自己的位置了，现在有M(1 ≦ M ≦ N - 2)个评委很快找到了自己的位置，剩下的N-M人找不到位置了，

需要给他们重新安排位置。

由于Lj希望自己的得分尽可能高。请你帮忙计算出LJ最后得分可能的最大值。

Solution

核心思想是二分$+dp$统计答案。

首先从小的情况考虑 满足三个中$>= mid$ 的条件是 两个都$>=mid$

所以$>=mid $ 的 为被确定的人才有贡献 事先统计下来

如何判断答案是否合法？我们的目的是让最后剩下的那个大于等于二分的$mid$。用一个$f[i]$表示让前$n$个第$i$个位置合法，之前最少需要多少个剩下$n−m$个中合法的但不确定的来补。

所以一开始如果是确定的并且$>=mid$，

那么$f$ 的 值是$0$ ,如果确定但$

把以上按顺序放到一个队列里，然后模拟删除操作即可。因为我们要使转移后的也合法，那么每次三个中至少有两个合法，所以每次在队列前三个中两两和取$min$入队即可。（转移当前需要至少多少个来补）

最后判断一下最后剩下的这个$f$是不是小于等于不确定位置中符合条件的数量即可。

Code

//

#include

using namespace std;

#define ll long long

#define inf 1000000000

#define maxnn 1000000

ll a[maxnn];

ll b[maxnn];

ll n,m;

ll D,P;

bool isok(ll ttt)

{

deque Q;Q.clear();

ll cnt=0;

for(int i=1;i<=n-m;i++)

if(b[i]>=ttt) cnt++;

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

{

if(!a[i]) Q.push_back(1);

else

if(a[i]>=ttt) Q.push_back(0);

else

if(a[i]

}

while(Q.size()>1)

{

int x1=Q.front(); Q.pop_front();

int x2=Q.front();Q.pop_front();

int x3=Q.front();Q.pop_front();

Q.push_back(min(min(x1+x2,x1+x3),min(x2+x3,inf)));

}

return Q.front()<=cnt;

}

int main()

{

cin>>n>>m;

ll l=0,r=0;

for(int i=1;i<=m;i++)

{

scanf("%lld%lld",&D,&P);

a[P]=D;

r=max(r,D);

}

for(int i=1;i<=n-m;i++)

{

scanf("%lld",&b[i]);r=max(r,b[i]);

}

ll ans=0;

while(l<=r)

{

ll mid=(l+r)/2;

if(isok(mid)) {ans=mid;l=mid+1;}

else r=mid-1;

}

cout<

}