二分答案
>=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;
- }
来源: http://www.bubuko.com/infodetail-2833568.html