2021CCPC华为云挑战赛
A.对象存储调度问题
贪心问题，使用优先队列(大顶堆)存一下分条，然后从小的对象开始填充。如果碰到无法填充的情况直接输出"No"，因为堆顶元素是堆里最大的，它装不下后面的也一样装不下。
#include using namespace std; const int N = 1e5 + 10; int a[N], b[N]; priority_queue<int> q; signed main(){ int t = 0; cin >> t; while(t--){ int n, m, flag = 1; cin >> n >> m; while (!q.empty()) q.pop(); for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + 1 + n); for (int i = 1, x; i <= m; i++){ cin >> x; q.push(x); } for (int i = n; i; i--){ int now = q.top(); q.pop(); if (a[i] > now){ cout << "No" << endl; flag = 0; break; } now -= a[i]; if (now) q.push(now); } if(!flag) continue; cout << "Yes" << endl; } return 0; }
B.卷业务模型分析
“这个序列是由两个给定的特征序列中的一个通过线性变换加上一定的随机抖动得来的。”
我们先分析一下样例：
显然， A 1 A1 A1序列跟 B B B序列根本不存在线性变换的近似关系。那么我们考虑如何去判定 A A A序列和 B B B序列之间的关系：
我们给出任意一个不单调函数，对其所有的点做 k k k倍乘变换，不难发现对于 k > 0 k>0 k>0每个点切线的斜率是一定在变大、 k < 0 k < 0 k<0斜率在变小，极值点除外。
我们可以在一个初始的 [ − ∞ , + ∞ ] [-∞,+∞] [−∞,+∞]取值范围上寻找 k k k的合适范围：通过三分法确定一个 k k k的大致范围，也就是通过三分法，每次比较偏差，找到最佳范围；再在该范围内找到一个最佳的 k k k，偏移量中位数为 b b b，就能找到最大偏差了。
#include #define ll long long using namespace std; const int N = 1e5 + 10; const ll MIN = -1e15 - 10, MAX = 1e15 + 10; int a1[N], a2[N], b[N], n = 0; ll calc1(int x) { ll maxn = MIN, minn = MAX; for (int i = 1; i <= n; i++) maxn = max(maxn, b[i] - 1ll * x * a1[i]), minn = min(minn, b[i] - 1ll * x * a1[i]); return (maxn - minn) / 2; } ll calc2(int x){ ll maxn = MIN, minn = MAX; for (int i = 1; i <= n; i++) maxn = max(maxn, b[i] - 1ll * x * a2[i]), minn = min(minn, b[i] - 1ll * x * a2[i]); return (maxn - minn) / 2; } ll work1() { int l = -1e6 + 10, r = 1e6 + 10; while (r - l >= 5) { int lmid = l + ((r - l) / 3), rmid = r - ((r - l) / 3); if (calc1(lmid) > calc1(rmid)) l = lmid; else r = rmid; } ll flag = 0, ans = 0; for (int i = l; i <= r; i++) { ll now = calc1(i); if (!flag || now < ans) ans = now, flag = 1; } return ans; } ll work2() { int l = -1e6 + 10, r = 1e6 + 10; while (r - l >= 5) { int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3; if (calc2(lmid) > calc2(rmid)) l = lmid; else r = rmid; } ll flag = 0, ans = 0; for (int i = l; i <= r; i++) { ll now = calc2(i); if (!flag || now < ans) ans = now, flag = 1; } return ans; } signed main(){ ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t = 0; cin >> t; while(t--){ cin >> n; for(int i = 1; i <= n; i++) cin >> a1[i]; for(int i = 1; i <= n; i++) cin >> a2[i]; for(int i = 1; i <= n; i++) cin >> b[i]; if(work1() < work2()) cout << 1 << endl; else cout << 2 << endl; } return 0; }
