题目一
解题思路
分类讨论
情况一：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 0 auto op0 = [&](int &idx0) { if (idx0 == -1) return; while (k && idx0) { swap(s[idx0], s[idx0 - 1]); k--; idx0--; } }; // Function to perform operation 1 auto 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; } 作者：清隆学长a 链接：https://www.nowcoder.com/discuss/630414252347568128 来源：牛客网
