Codeforces Round 935 (Div. 3)

A. Setting up Camp（模拟）

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;int main(){int t, n;scanf("%d", &t);int a, b, c;while(t--){scanf("%d%d%d", &a, &b, &c);int x = b / 3, y = b % 3;if(y != 0 && y + c < 3) printf("-1\n");else{int tt;if(y == 0 && c != 0) tt = (c - 1) / 3 + 1;else{int z = y + c;if(z % 3 == 0) tt = z / 3;else tt = z / 3 + 1;}int res = a + x + tt;printf("%d\n", res);}}return 0;
}

B. Fireworks（思维）

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 2e5 + 10;signed main(){int t, n;scanf("%d", &t);int a, b, m;while(t--){scanf("%lld%lld%lld", &a, &b, &m);int cnt = m / a + 1 + m / b + 1;printf("%lld\n", cnt);}return 0;
}

C. Left and Right Houses（前缀和）

先预处理 1 个数前缀和，如果左边 0 和 右边 1 都大于等于 一半，那就取离中点最近的点

#include<iostream>
using namespace std;
const int N = 3e5 + 10;
char a[N];
int b[N];int main(){int t, n;scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 1; i <= n; i++) cin>>a[i];for(int i = 0; i <= n; i++) b[i] = 0;for(int i = 1; i <= n; i++){b[i] = b[i - 1] + (a[i] == '1');}int res = 1e9, ans = 1e9;for(int i = 0; i <= n; i++){if(i - b[i] < (i + 1) / 2) continue;if(b[n] - b[i] < (n - i + 1) / 2) continue;if(abs(i - n / 2) < res){res = abs(i - (n + 1) / 2);ans = i;}}printf("%d\n", ans);//cout<<"-----------------------"<<endl;}return 0;
}

D. Seraphim the Owl（前缀和）

先求 m 后最小的值，然后求 a[i] + b[i + 1] 的最小值，b 为后缀和数组

#include<iostream>
using namespace std;
const int N = 2e5 + 10;
long long a[N], b[N];int main(){int t;scanf("%d", &t);int n, m;while(t--){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);long long ans = 0;for(int i = 1; i <= n; i++){scanf("%lld", &b[i]);if(i > m) ans += min(a[i], b[i]);}b[m + 1] = 0;for(int i = m; i >= 1; i--){b[i] += b[i + 1];}long long res = 1e18;for(int i = 1; i <= m; i++){res = min(res, a[i] + b[i + 1]);}ans += res;printf("%lld\n", ans);}return 0;
}

E. Binary Search（二分）

先看看这个求的值在不在二分边界处，如果在就不用交换，如果不在，那就交换到边界处

#include<iostream>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int n, x;int main(){int t;scanf("%d", &t);while(t--){scanf("%d%d", &n, &x);int pos = 0;for(int i = 1; i <= n; i++){scanf("%d", &a[i]);if(a[i] == x) pos = i;}int l = 1, r = n + 1;while(l + 1 < r){int mid = (l + r) / 2;if(a[mid] <= x) l = mid;else r = mid;}if(a[l] == x){printf("0\n");}else{printf("1\n");printf("%d %d\n", pos, l);}}return 0;
}