题目一
解题思路
分类讨论
情况一:5元汉堡也买不完。
情况二:5元汉堡能买完,非5元买不起。
情况三:都能买起,或还有剩余买原价汉堡。
题目二
解题思路
找规律,假设有...xy...,x在前。如果交换x、y后,x没有到最右边,且y没有到最左边,那么x、y还是同时作为十位和个位,对结果不影响。
如果y到最左边,会影响个位,比如010变100,结果从11变为10.
如果x到最右边,会影响十位,比如010变001,结果从11变为1.
要想结果最小,先尝试将最右的1移到最右边,再尝试将最左的1移到最左边。
#include <bits/stdc++.h>using namespace std;void solve() {int n, k;cin >> n >> k;string s;cin >> s;int idx0 = s.find('1');int idx1 = s.rfind('1');// Function to perform operation 0auto op0 = [&](int &idx0) {if (idx0 == -1) return;while (k && idx0) {swap(s[idx0], s[idx0 - 1]);k--;idx0--;}};// Function to perform operation 1auto op1 = [&](int &idx1) {if (idx1 == -1) return;while (k && idx1 < n - 1) {swap(s[idx1], s[idx1 + 1]);idx1++;k--;}};if (n - idx1 - 1 <= k)op1(idx1);op0(idx0);int res = 0;for (int i = 0; i < n - 1; i++)res += stoi(s.substr(i, 2));cout << res << "\n"; }int main() {int T;cin >> T;while (T--)solve();return 0; }
题目三
解题思路
解法一:暴力。每次遍历得到最长最靠左的子串,然后erase删除。
解法二:
可以维护一个集合,存储当前所有连续相同字符构成的子串的信息(子串长度、左右端点位置)。每次从集合中取出长度最大的子串删除,并更新相邻子串的信息。重复此过程,直到集合为空。时间复杂度为 O(NlogN)。
#include <bits/stdc++.h> using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;string s;cin >> s;char last = s[0];int cnt = 1, left = 0;map<int, array<int, 3>> mpl, mpr;set<array<int, 3>> se;for (int i = 1; i < n; i++) {if (s[i] != last) {se.insert({-cnt, left, i - 1});mpl[left] = {i - 1, last, cnt};mpr[i - 1] = {left, last, cnt};left = i;cnt = 1;last = s[i];} else {cnt++;}}se.insert({-cnt, left, n - 1});mpl[left] = {n - 1, last, cnt};mpr[n - 1] = {left, last, cnt};int res = 0;while (!se.empty()) {auto fi = *se.begin();auto [cnt, l, r] = fi;char lc = mpr[l - 1][1];char rc = mpl[r + 1][1];if (lc == rc) {int lidx = mpr[l - 1][0];int ridx = mpl[r + 1][0];int lcnt = mpr[l - 1][2];int rcnt = mpl[r + 1][2];se.erase({-lcnt, lidx, l - 1});se.erase({-rcnt, r + 1, ridx});se.insert({-(lcnt + rcnt), lidx, ridx});mpl.erase(r + 1);mpr.erase(l - 1);mpl[lidx] = {ridx, lc};mpr[ridx] = {lidx, lc};}se.erase(fi);mpr.erase(l);mpl.erase(r);if (se.empty()) break;res++;}cout << res << "\n";return 0; }
题目四
解题思路
如果暴力枚举,随着枚举的平均值一直增大,能找到满足条件的区间越难。所以会出现true、ture。。。true、false、false这样的非递增序列。既然是有序的,那么就可以用二分法枚举平均值,然后在O(n)的时间复杂度下检测这个平均值是否能满足,如果能,平均值可以继续增大,否则减小。
检测平均值avg是否能满足,从m开始,遍历到n,并且维护一个区间,使得该区间大于等于m且平均值大于等于avg。这可以通过建立一个前缀和(减去平均值,这样只有区间和大于等于0既可满足),记录当前位置i的前m个及以前的最小前缀和,来保持当前区间和最大。
#include <iostream> #include <cstdio> #include <algorithm>using namespace std;const int MAXN = 100005; int arr[MAXN]; double sum[MAXN]; int n, m;bool check(double avg) {for (int i = 1; i <= n; ++i) {sum[i] = sum[i - 1] + arr[i] - avg;}double minv = 0;for (int i = m; i <= n; ++i) {minv = min(minv, sum[i - m]);if (sum[i] >= minv) {return true;}}return false; }int main() {int T;cin >> T;while (T--) {cin >> n >> m;double l = 0, r = 0;for (int i = 1; i <= n; ++i) {cin >> arr[i];r = max(r, (double) arr[i]);}while (r - l > 1e-5) {double mid = (l + r) / 2;if (check(mid)) {l = mid;} else {r = mid;}}printf("%.3f\n", r);}return 0; }