ACM下学期第五次周赛

C题拼数字

题目意思是给定一组数字，将这些数字拼到一起，然后组成一个最大的数字。

题目不是很难，只需要将元素组先排序再去从大到小依次输出即可，但是有一种特殊情况需额外考虑，如90和9这组数据，如果按照上面所说去拼，发现拼出来的909并没有990大，所以说只排序是不行的，所以我们需要自定义排序，去判断a,b拼成的数字大还是b,a拼成的数字大。还有一种特殊情况就是全是零，这种情况我们只需要输出0即可。（数据中没有考虑这个情况，故以下代码可以过）

#include <bits/stdc++.h> using namespace std; bool compare(const string &a, const string &b) { return a + b > b + a; } int main() { int n; cin >> n; vector<string> nums(n); for (int i = 0; i < n; ++i) { cin >> nums[i]; } sort(nums.begin(), nums.end(), compare); for(int i=0;i<n;i++) cout<<nums[i]; return 0; }

D题加和减

题目描述为给定一个数组，小红可以进行以下的操作：

每次操作可以让某个数加 1 或者某个数减 1 。
小红最多能进行 k 次操作。

要去小红操作结束后，该数组出现次数最多的元素次数尽可能多。

因为数可以随即加减，并无区间的限制，所以我们可以先进行排序，排完序之后我们就要模拟题目中的操作了，要如何确定统一变成某个数且成本控制在K之内呢？我们应该可以联想到，一个有序区间内将所有数变成中位数的代价是最小的，所以我们可以用双指针去确定区间，然后再定义中位数，将该区间内的所有数据，都变成中位数看看是需要多少次，并且使数量最多。这里用前缀和的原因是在计算区间内所有数据都变成中位数的时候，需要不断求和，所以如果不提前预处理求和，每次在循环内进行求和会导致时间超限。

计算中位数左边需要的次数公式为：a[mid] * (mid - left) - (pref[mid] - pref[left]))

mid-left 是计算中位数左边数据的个数；

计算中位数右边需要的次数公式为：(pref[right + 1] - pref[mid + 1]) - a[mid] * (right - mid)

同理，right-mid是计算 中位数右边数据的个数；

最后max去不断刷新最大个数；

最终输出ans;

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int n; ll k; cin >> n >> k; vector<ll> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; sort(a.begin(), a.end()); vector<ll> pref(n + 1, 0); for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i]; int ans = 0; int left = 0; for (int right = 0; right < n; ++right) { while (left <= right) { int mid = (left + right) / 2; ll cost = (a[mid] * (mid - left) - (pref[mid] - pref[left])) + ((pref[right + 1] - pref[mid + 1]) - a[mid] * (right - mid)); if (cost <= k) break; ++left; } ans = max(ans, right - left + 1); } cout << ans << "\n"; return 0; }