https://vjudge.net/contest/375686#overview
A - Sorted Adjacent Differences
从小到大排序，最后一个减最前面一个的差最大，并且倒数第二个减去第一个比刚刚的差值小，循环着输出就行了
#include <iostream> #include <algorithm> using namespace std; const int N = 1e5 + 10; int t, n, a[N], b[N]; int main() { cin >> t; while(t--){ cin >> n; for(int i = 1;i <= n; ++ i) cin >> a[i]; sort(a + 1, a + 1 + n); int s = 1, e = n, k = n; while(s <= e) { b[k--] = a[e--]; b[k--] = a[s++]; } for(int i = 1;i <= n; ++ i) cout << b[i] << " "; cout << endl; } }
B - Powered Addition
记录最大与最小的差值，位运算数位数即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> inline void read(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return ; while (c != ‘-‘ && (c < ‘0‘ || c > ‘9‘)) c = getchar(); sgn = (c == ‘-‘) ? -1:1; ret = (c == ‘-‘) ? 0:(c - ‘0‘); while (c = getchar(), c >= ‘0‘ && c <= ‘9‘) ret = ret * 10 + (c - ‘0‘); ret *= sgn; return ; } template <class T> inline void out(T x) { if (x > 9) out(x / 10); putchar(x % 10 + ‘0‘); } int t; void solve(){ int n, res = 0; read(n); vector<ll> a(n); for(int i = 0;i < n; ++ i) read(a[i]); ll l= a[0], m = 0; for(int i = 0;i < n; ++ i){ l = max(a[i], l); m = max(l - a[i], m); } while(m) m >>= 1, res ++; out(res); puts(""); } int main() { ios_base::sync_with_stdio(false); read(t); while(t--) solve(); }
从大到小排序， 依次取平均，有一个小于目标就失败了
#include <bits/stdc++.h> using namespace std; typedef long long ll; void solve() { int n, x; cin >> n >> x; vector<int> v(n); for(int i = 0;i < n; ++ i) cin >> v[i]; sort(v.begin(),v.end(), greater<int>()); ll sum = 0; for(int i = 0;i < n; ++ i){ sum += v[i]; if(sum / (i + 1) < x){ cout << i << "\n"; return ; } } cout << n << "\n"; } int main() { ios_base::sync_with_stdio(false); int t; cin >> t; while(t--) solve(); }
记录被b[i[伤害后的血量，求个sum。需要有一个对着满血的怪开枪，a[i] - b[i-1] (i > 1), 所以应该加上最小的b[i-1], 也就是min{a[i] - c[i}];
#include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> inline void read(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return ; while (c != ‘-‘ && (c < ‘0‘ || c > ‘9‘)) c = getchar(); sgn = (c == ‘-‘) ? -1:1; ret = (c == ‘-‘) ? 0:(c - ‘0‘); while (c = getchar(), c >= ‘0‘ && c <= ‘9‘) ret = ret * 10 + (c - ‘0‘); ret *= sgn; return ; } void solve(){ int n; read(n); vector<ll> a(n), b(n), c(n); for(int i = 0;i < n; ++ i){ read(a[i]), read(b[i]); } c[0] = max(0ll, a[0] - b[n-1]); ll sum = c[0], k = a[0] - c[0]; for(int i = 1;i < n; ++ i){ c[i] = max(0ll, a[i] - b[i-1]); sum += c[i]; k = min(k, a[i] - c[i]); } printf("%lld\n",sum+k); } int main() { ios_base::sync_with_stdio(false); int t; read(t); while(t--) solve(); }
a[i]前面有1可以解决b[i] > a[i], 有-1可以解决b[i] < a[i];
#include <bits/stdc++.h> using namespace std; typedef long long ll; template <typename T> inline void read(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return ; while (c != ‘-‘ && (c < ‘0‘ || c > ‘9‘)) c = getchar(); sgn = (c == ‘-‘) ? -1:1; ret = (c == ‘-‘) ? 0:(c - ‘0‘); while (c = getchar(), c >= ‘0‘ && c <= ‘9‘) ret = ret * 10 + (c - ‘0‘); ret *= sgn; return ; } template <class T> inline void out(T x) { if (x > 9) out(x / 10); putchar(x % 10 + ‘0‘); } void solve(){ int n; read(n); vector<int> a(n), b(n); for(int i = 0;i < n; ++ i) read(a[i]); for(int i = 0;i < n; ++ i) read(b[i]); int cnt1 = 0, neg_cnt1 = 0; if(a[0] != b[0]){ puts("NO"); return ; } if(a[0] == 1) cnt1 ++; if(a[0] == -1) neg_cnt1 ++; for(int i = 1;i < n; ++ i){ if(cnt1 && neg_cnt1){ puts("YES"); return ; } if(b[i] > a[i] && cnt1 == 0){ puts("NO"); return ; } if(b[i] < a[i] && neg_cnt1 == 0){ puts("NO"); return ; } if(a[i] == 1) cnt1 ++; if(a[i] == -1) neg_cnt1 ++; } puts("YES"); } int main() { ios_base::sync_with_stdio(false); int t; read(t); while(t--) solve(); }
原文：https://www.cnblogs.com/DefineWaAc/p/12986979.html