BZOJ 4985: 评分

二分答案

>=key的记为1

f[i]表示令i位置为1所需要的最少的1的个数

队列模拟

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,ans,d[1000005],a[1000005],stack[1000005];
int check(int key){
int ans=0;
for (int i=1; i<=n-m; i++) if (d[i]>=key) ans++;
int head=0,tail=0;
for (int i=1; i<=n; i++){
if (!a[i]) stack[++tail]=1;
else if (a[i]>=key) stack[++tail]=0;
else stack[++tail]=1e9;
}
while (tail-head+1>=3){
int x1=stack[++head],x2=stack[++head],x3=stack[++head];
stack[++tail]=min(x1+x2,min(x1+x3,min(x2+x3,(int)1e9)));
}
return stack[tail]<=ans;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1; i<=m; i++){
int x,y;
scanf("%d%d",&x,&y);
a[y]=x;
}
for (int i=1; i<=n-m; i++) scanf("%d",&d[i]);
int l=0,r=1e9;
while (l<r){
int mid=(l+r+1)>>1;
if (check(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
return 0;
}