E. Klee's SUPER DUPER LARGE Array!!!
https://codeforces.com/contest/2009/problem/E
思路：
题目让我们求从k开始的n个数的前k个数的和与剩下的数的和的差最小是多少，可以用数学思维O(1)求解，都是我数学比较差，我们这里用二分。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define pb push_back
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define lowbit(x) x&(-x)
#define pll pair<int,int>
const int N = 3e5 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9+7;
using namespace std;
int ss(int a, int b) {return ((a + b) * (b - a + 1)) / 2;
}
void solve() {int n, k;cin >> n >> k;int l = 1, r = n-1;int ans;while (l <= r) {int mid = l + r >> 1;if (ss(k, k + mid - 1) < ss(k + mid, k + n - 1)) ans=mid,l = mid + 1;else ans=mid,r = mid - 1;}int res = 1e20;for (int i = max(1ll,ans - 10); i <= ans + 10&&i<n; i++) {res = min(res, abs(ss(k, k + i - 1) - ss(k + i, k + n - 1)));}cout << res << '\n';}
signed main() {ios; TESTsolve();return 0;
}D. Wooden Toy Festival
https://codeforces.com/contest/1840/problem/D
思路：
很明显是一道二分答案的题目，所以我们只需要考虑判断函数怎么写即可，我们发现我们只需要安排的雕刻师不大于三即可，我们可以对数组排序，我们看看每一个雕刻师最多保证答案不会超出界限，最后判断我们使用的雕刻师数量即可。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define pb push_back
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define lowbit(x) x&(-x)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;
int n, a[N];
bool check(int x) {//安排几个人int cnt = 0;int pre = a[1];for (int i = 1; i <= n; i++) {if ((a[i] - pre + 1) / 2 <= x) {}else {pre = a[i];cnt++;}if (cnt >= 3) return false;}return cnt < 3;
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);int l = 0, r = 1e9;int ans;while (l <= r) {int mid = l + r >> 1;if (check(mid)) ans=mid,r = mid-1;else l = mid + 1;}cout << ans << '\n';
}
signed main() {ios; TESTsolve();return 0;
}
分巧克力
1227. 分巧克力 - AcWing题库
思路：
只要知道一个长为h，宽为w的巧克力可以分成（h/x)*(w/x)个边长为x的正方形巧克力即可。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define pb push_back
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define lowbit(x) x&(-x)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;int n, k;
int h[N], w[N];
bool check(int x) {int res = 0;for (int i = 1; i <= n; i++) {res += (h[i] / x) * (w[i] / x);if (res >= k) return true;}return res >= k;
}
void solve()
{cin >> n >> k;for (int i = 1; i <= n; i++) cin >> h[i] >> w[i];int l = 1, r = 1e9, ans;while (l <= r) {int mid = l + r >> 1;if (check(mid)) {ans = mid;l = mid + 1;}else {r = mid - 1;}}cout << ans << '\n';
}
signed main() {ios; solve();return 0;
}
4001. 训练
4001. 训练 - AcWing题库
思路：
用二分求出每个位置有多少个数比他小，再在每次的关系中判断，如果有关系的位置中，恰好这个位置是比你小的数，则答案减一。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define pb push_back
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define lowbit(x) x&(-x)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;bool cmp(pll a, pll b) {return a.first < b.first;
}
void solve()
{int n, k;cin >> n >> k;vector<pll>r(n + 1);vector<int>a(n + 1);vector<int>b(n + 1);for (int i = 1; i <= n; i++) {cin >> r[i].first;r[i].second = i;a[i] = r[i].first;b[i] = r[i].first;}vector<int>cnt(n + 1);sort(r.begin() + 1, r.end(), cmp);sort(a.begin() + 1, a.end());for (int i = 1; i <= n; i++) {int pos=lower_bound(a.begin()+1, a.end(), a[i]) - a.begin();cnt[r[i].second] = pos - 1;}for (int i = 1; i <= k; i++) {int x, y;cin >> x >> y;if (b[x] > b[y]) cnt[x] = max(0ll, cnt[x] - 1);if (b[y] > b[x]) cnt[y] = max(0ll, cnt[y] - 1);}for (int i = 1; i <= n; i++) cout << cnt[i] << ' ';
}
signed main() {ios; solve();return 0;
}