Solution
核心思想是二分$+dp$统计答案。
首先从小的情况考虑 满足三个中$>= mid$ 的条件是 两个都$>=mid$
所以$>=mid $ 的 为被确定的人才有贡献 事先统计下来
如何判断答案是否合法？我们的目的是让最后剩下的那个大于等于二分的$mid$。用一个$f[i]$表示让前$n$个第$i$个位置合法，之前最少需要多少个剩下$n−m$个中合法的但不确定的来补。
所以一开始如果是确定的并且$>=mid$，
那么$f$ 的 值是$0$ ,如果确定但$<mid$ ,$f$ 的 值是$inf$ 。如果不确定 ，那么就是$1$ (放一个合法的)
把以上按顺序放到一个队列里，然后模拟删除操作即可。因为我们要使转移后的也合法，那么每次三个中至少有两个合法，所以每次在队列前三个中两两和取$min$入队即可。（转移当前需要至少多少个来补）
最后判断一下最后剩下的这个$f$是不是小于等于不确定位置中符合条件的数量即可。
Code
// #include<bits/stdc++.h> 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 <ll > 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]<ttt) Q.push_back(inf); } 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<<r; }
原文：https://www.cnblogs.com/OIEREDSION/p/11370970.html