교육 Codeforces Round 87 D. Multiset (2 점)

제목 링크
전송 문
제목 의 대의
집합 (요소 중복 허용) 을 보 여 줍 니 다. 크기 는 n n 입 니 다.두 가지 조작 이 있 습 니 다.

이 집합 에 원소 k k k 를 추가 합 니 다

집합 에서 k k k 작은 요소 삭제

입력 에 따라 모든 작업 을 수행 한 후 집합 에 존재 하 는 원 소 를 출력 하고 집합 이 비어 있 으 면 0 0 을 출력 합 니 다.
제목 분석
첫 번 째 방법: 데이터 구조: 가중치 선분 트 리 o r or or 평형 트 리 o r or or 나무 모양 배열 을 사용 하지만 시간 을 초과 할 수 있 습 니 다. n n 의 범위: [1, 1, 0 6] [1, 10 ^ 6] [1, 106]
두 번 째 방법: 제목 은 하나의 요소 만 출력 하기 때 문 입 니 다.그래서 우 리 는 일련의 조작 을 거 친 후에 집합 에서 가장 작은 요 소 를 찾 으 려 고 한다.방법: 2 분 이 최소 원소 의 값 m i n minn minn.
2 분: 구간: l = 0, r = n + 1 l = 0, r = n + 1 l = 0, r = n + 1, m i d = (l + r) / 2 mid = (l + r) / 2 mid = (l + r) / 2 mid = (l + r) / 2.하나의 수 x x x 에 대해 x ≥ m i n x \ g minn x ≥ minn 이면 x x 는 2 분 의 c h e c k check 을 통과 하고 그렇지 않 으 면 통과 하지 않 는 다.추가 분석: 만약 에 m i d mid mid 가 2 분 의 c h e c k check check 을 통과 하면 답 은 m i d mid mid 또는 m i d mid mid 보다 작 기 때문에 r = m i d r = mid r = mid r = mid;만약 에 m i d mid mid 가 2 점 을 통과 하지 못 하면 정 답 이 m i d mid mid 보다 크 거나 집합 이 비어 있 기 때문에 l = m i d + 1 l = mid + 1 l = mid + 1 l = mid + 1.
c h e c k check: 집합 을 두 부분 으로 나 눕 니 다. 하 나 는 x x x x 보다 작고 다른 하 나 는 x x x x 보다 크 며 각각 두 부분의 수량 c n t 1, c n t 2 cnt 1, cnt 2 cnt 1, cnt 2 cnt 1, cnt 2 를 얻 습 니 다.다음은 c n t 1, c n t 2 cnt 1, cnt 2 cnt 1, cnt 2 cnt 1, cnt 2 에 대한 수정 을 진행 하면 됩 니 다.c h e c k check 통과 하지 않 는 조건: 작업 도중에 첫 번 째 부분의 수량 c n t 1 < 0 cnt 1 < 0 cnt 1 < 0 cnt 1 < 0.또는 완전 부 작업 을 끝 낸 후 첫 번 째 부분의 수량 c n t 1 = 0 cnt 1 = 0 cnt 1 = 0 cnt 1 = 0.
집합 이 비어 있 는 상황 을 잘 처리 해 야 합 니 다.
코드

#include 
using namespace std;
const int maxn = 1e6+5;
int n, q;
int a[maxn];
int k[maxn];

bool check(int x) {
	int cnt1 = 0, cnt2 = 0;
	for(int i = 1; i <= n; i++) {
		if(a[i] <= x) cnt1++;
		else cnt2++;
	}
	
	for(int i = 1; i <= q; i++) {
		if(k[i] < 0) {
			if(-k[i] <= cnt1) cnt1--;
			else cnt2--;
		}
		else {
			if(k[i] <= x) cnt1++;
			else cnt2++;
		}
		
		if(cnt1 == -1) return false;
	}
	
	if(cnt1 == 0) return false;
	else return true;
}

int main() {
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= q; i++) scanf("%d", &k[i]);
	
	int l = 0, r = n+1;
	while(l < r) {
		int mid = (l+r)/2;
		if(check(mid)) r = mid;
		else l = mid+1;
	}
	
	if(l == n+1) printf("0
");
	else printf("%d
", l);
	return 0;
}