20240531训练二分题

本文主要是介绍20240531训练二分题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二分

题目描述

有一个由 $n$ 个整数组成的序列，从左到右编号为 $1$ 到 $n$ 。这些整数有两种颜色，分别是 $0$ 和 $1$ ，每个整数正好有一种颜色。这些整数按照从 $1$ 到 $n$ 的编号顺序进入多集合 $S_1$ 。

每当一个新的整数 $x$ 进入 $S_1$ 时，你必须在 $S_1$ 中选择一个颜色与 $x$ 不同的整数 $y$ 与 $x$ 发生反应，使得 $x$ 和 $y$ 消失，反应产物 $x+y$ 插入另一个集合 $S_2$ 。如果不存在这样的 $y$ ，则不会发生反应，只有 $x$ 被插入 $S_1$ 。

给定整数序列和每个整数的颜色，求处理最后一个元素后 $S_2$ 中最小元素的最大可能值。

输入

第一行包含一个整数 $n$ ( $2\le n\le 10^5$ )，代表整数个数。

第二行包含 $n$ 个正整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le 10^8$ )，代表整数序列。

第三行包含 $n$ 个整数 $c_1,c_2,\dots ,c_n$ ( c i ∈ { 0 , 1 } c_i\in \{0,1\} ci​∈{0,1} )，其中 $c_i$ 代表 $i$ 个整数的颜色。

可以保证至少有一个 $i$ 是 $c_i=0$ ，至少有一个 $j$ 是 $c_j=1$ 。

输出

输出一个整数，代表答案。

样例

input1:
4
1 3 2 4
0 0 1 1
inout1:
5input2:
6
1 3 4 2 5 6
0 1 0 1 0 1
inout2:
4input3:
7
3 3 4 4 5 3 1
0 0 1 1 1 0 0
inout3:
7

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],c[N];
bool check(int mid)
{multiset<int>se;//int col=-1;for(int i=1;i<=n;i++){if(se.size()&&c[i]!=col){int f=mid-a[i];auto l=se.lower_bound(f);if(l!=se.end())	se.erase(l);else	return 0;}else{se.insert(a[i]);col=c[i];}}return 1;
}
int main()
{cin>>n;for(int i=1;i<=n;i++)	cin>>a[i];for(int i=1;i<=n;i++)	cin>>c[i];int l=0,r=1e9;while(l<r){int mid=(l+r+1)/2;if(check(mid))	l=mid;else	r=mid-1;}cout<<l;return 0;
}

这篇关于20240531训练二分题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---