本文主要是介绍2022 icpc 南京站 G. Inscryption - 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题面
分析
重点是0怎么处理，怎么选择，可以二分0选择-1的次数，将所有0选-1的都放在最后就可以得出答案。
代码
#include <bits/stdc++.h>using namespace std;
using ll = long long;const int N = 1e6 + 10;int a[N];
int n;
int sum;int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}bool check(int mid) {int cnt = sum - mid;int p = 1, q = 1;for(int i = 0; i < n; i ++) {if(a[i] == 1) p ++, q ++;else if(a[i] == -1) {if(q < 2) {return false;}q --;}else {if(cnt > 0) {cnt --;p ++, q ++;}else {if(q < 2) return false;q --;}}}return true;
}void solve() {cin >> n;sum = 0;for(int i = 0; i < n; i ++) {cin >> a[i];if(a[i] == 0) sum ++;}int l = 0;int r = sum;while(l < r) {int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}int p = 1;int q = 1;int cnt = sum - l;for(int i = 0; i < n; i ++) {if(a[i] == 1) p ++, q ++;else if(a[i] == -1) {if(q < 2) {cout << "-1\n";return ;}q --;}else {if(cnt > 0) {cnt --;q ++;p ++;}else {if(q < 2) {cout << -1 << "\n";return ;}q --;}}}int res = gcd(p, q);if(res) {p /= res;q /= res;}cout << p << ' ' << q << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {solve();}
}
这篇关于2022 icpc 南京站 G. Inscryption - 二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
