请问dalao为啥右边界k初始值是n+1啊?不应该是n吗
  • 板块P9050 [PA2021] Sumy
  • 楼主osun
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/13 23:09
  • 上次更新2023/11/14 12:04:53
查看原帖
请问dalao为啥右边界k初始值是n+1啊?不应该是n吗
1049817
osun楼主2023/11/13 23:09
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;
using ll = long long;
const int M = 5e5 + 9;
typedef pair<int, int>P;
P a[M];
int n;
string ans[M];

bool check(int x) {
	ll fw = a[x].first;
	for (int i = 1; i <= n; i++) {
		if (i != x) {
			if (a[i].first < fw)fw += a[i].first;
			else return 0;
		}
	}
	return 1;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) { cin >> a[i].first; a[i].second = i; }
	sort(a + 1, a + n + 1);
	int j = 1; int k = n+1;
	while (j < k) {
		int mid = k + j >> 1;
		if (check(mid))k = mid;
		else j = mid + 1;
	}
	for (int i = 1; i <= n; i++) {
		if (i >= k)ans[a[i].second] = 'T';
		else ans[a[i].second] = 'N';
	}
	for (int i = 1; i <= n; i++)cout << ans[i];
	return 0;
}
2023/11/13 23:09
加载中...