LOJ#2764. 「JOI 2013 Final」JOIOI 塔

题目地址

题解

真的想不到二分...不看tag的话...

考虑二分答案转化为判定问题，那么问题就变成了能不能组合出x个JOI/IOI，考虑贪心判定，倒着做，统计I的个数cnt，已组OI的个数tot，以及JOI/IOI个数ans。对于J显然直接找一个OI组成答案。对于O显然直接找I。对于I需要贪心考虑，假设目前的cnt+tot+ans>=x那么就组答案，否则做OI里面的那个I，让cnt++。（贪心考虑只需要造x个OI，造多了会浪费）

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1000010;

int n;

char s[N];

bool check(int x) {

	int ans = 0, tot = 0, cnt = 0;

	for(int i = n; i; --i) {

		if(x == ans) return 1;

		if(s[i] == 'J') {

			if(tot) --tot, ++ans;

			continue;

		}

		if(s[i] == 'O') {

			if(cnt) --cnt, ++tot;

			continue;

		}

		if(s[i] == 'I') {

			if(ans + tot + cnt < x) cnt++;

			else {

				if(tot) --tot, ++ans;

			}

		}

	}

	if(x == ans) return 1;

	return 0;

}

int main() {

	scanf("%d%s", &n, s + 1);

	int l = 0, r = n, ans = 0;

	while(l <= r) {

		int mid = (l + r) >> 1;

		if(check(mid)) ans = mid, l = mid + 1;

		else r = mid - 1;

 	}

 	printf("%d\n", ans);

}

巴特西

LOJ#2764. 「JOI 2013 Final」JOIOI 塔

题目地址

题解

最新文章

热门文章