思路：
分别记录字母A, B, C的数量，显然要满足B的数量等于A的数量和C的数量的和才行
#include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 100010; int a[N]; vector<PII>index[100010]; int main() { int T; cin >> T; while (T--) { string s; cin >> s; int cnta = 0, cntb = 0, cntc = 0; for (int i = 0; i < s.size(); i++) if (s[i] == 'A') cnta++; else if (s[i] == 'B') cntb++; else if (s[i] == 'C') cntc++; if (cntb == cnta + cntc) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
题意：
题意有点难懂，意思是给你规定了一种操作，问要怎么进行一些列的这种操作才能使原数组递增
思路：
比赛的时候想了了土方法，类比冒泡排序从后往前枚举，遇到一个逆序对（a[i] > a[j]且，i < j）就整体前移一个，由于这个题数据范围只有50，所以O(n^3)完全ok的
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 55; vector<PII>index[100010]; int main() { int T; cin >> T; while (T--) { int n; cin >> n; int a[N]; for (int i = 1; i <= n; i++) cin >> a[i]; int tmp[N], b[N]; for (int i = 1; i <= n; i++) tmp[i] = a[i], b[i] = a[i]; sort(tmp + 1, tmp + 1 + n); bool flag = true; for (int i = 1; i <= n; i++) if (tmp[i] != a[i]) flag = false; if (flag) { cout << 0 << endl; continue; } //else int k = 0; //k是逆序对的数量 for (int i = n; i >= 1; i--) for (int j = i - 1; j >= 1; j--) if (b[i] < b[j]) { int x = b[j];//整体往前一个 for (int p = j; p <= i - 1; p++) b[p] = b[p + 1]; b[i] = x; k++; } cout << k << endl; int l = 0, r = 0, d = 1; for (int i = n; i >= 1; i--) for (int j = i - 1; j >= 1; j--) if (a[i] < a[j]) { cout << j << ' ' << i << ' ' << 1 << endl; int x = a[j];//整体往前一个 for (int p = j; p <= i - 1; p++) a[p] = a[p + 1]; a[i] = x; } } return 0; }
思路：
优先队列，同时再开一个idx数组记录两个交谈的人的下标，每次取出两个队头元素，然后判断是否大于1，大于一都自减一，然后再放回队列，直到队列中 元素只有一个或没有，需要注意的是，我们刚开始往队列中加元素的时候只存大于0的元素
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 200010; int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { int n; cin >> n; vector<PII>idx; idx.clear(); priority_queue<PII>q; for (int i = 1; i <= n; i++) { int x; cin >> x; if(x) q.push({ x, i }); } while (q.size() > 1) { auto a = q.top(); q.pop(); auto b = q.top(); q.pop(); idx.push_back({ a.second, b.second }); if (a.first - 1 > 0) q.push({ a.first - 1, a.second }); if (b.first - 1 > 0) q.push({ b.first - 1, b.second }); } if (q.size()) q.pop(); cout << idx.size() << endl; for (int i = 0; i < idx.size(); i++) cout << idx[i].first << ' ' << idx[i].second << endl; } return 0; }
E1. Permutation Minimization by Deque
思路：
贪心 + 双端队列，每次比较和队头元素的大小，大于队头元素就插到队尾，小于就插到队首
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 200010; int a[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { memset(a, 0, sizeof a); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; deque<int>q; q.push_back(a[1]); for (int i = 2; i <= n; i++) if (a[i] < q.front()) q.push_front(a[i]); else q.push_back(a[i]); for (auto x : q) cout << x << ' '; cout << endl; } return 0; }
上了119分，还行吧