比赛链接：Here
1315A. Dead Pixel
签到题，
比较四个值
max(max(x, a - 1 - x) * b, a * max(y, b - 1 - y))
1315B. Homecoming
\(A\to B\) 花费 \(a\) 元
\(B\to A\) 花费 \(b\) 元
求要走到点 \(i\)，从 \(i\) 上车能在 \(p\) 内到终点。
这个挺多解法的
- 二分答案
- 逆推模拟
- DP
虚拟赛的时候写了DP
const int N = 1e6 + 10;
ll f[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; for (cin >> _; _--;) {
int a, b, p; cin >> a >> b >> p;
string s; cin >> s;
int n = s.size();
if (s[n - 1] == ‘A‘) f[n - 1] = a;
else f[n - 1] = b;
f[n] = 0;
ll pos = n - 1;
for (int i = n - 2; i >= 0; --i) {
if (i == n - 2) f[i] = (s[i] == ‘A‘ ? a : b);
else if (s[i] == s[i + 1]) f[i] = f[i + 1];
else f[i] = f[i + 1] + (s[i] == ‘A‘ ? a : b);
}
for (int i = 0; i < n; ++i)
if (f[i] <= p) {pos = i; break;}
cout << pos + 1 << "\n";
}
}
1315C. Restoring Permutation
题意：
给一组长度为 \(n\) 的 \(b[i]\) , 让你找一组长度为 \(2n\) 的 \(a[i]\) , 满足 \(b[i] = min(a[2*i-1 ] ,a[2*i])\) ,并且字典序最小 。
AtCoder 上做过类似的，直接考虑贪心
const int N = 1e4 + 10;
ll a[N], b[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; for (cin >> _; _--;) {
ll n;
cin >> n;
map<ll, ll> mp;
for (int i = 1; i <= n; ++i) {
cin >> b[i], mp[b[i]] = 1;
}
bool f = 1;
for (int i = 1;f and i <= n; ++i) {
a[i * 2 - 1] = b[i];
ll k = b[i];
while (mp[k] == 1) k += 1;
if (k <= 2 * n) {
a[i * 2] = k;
mp[k] = 1;
} else f = 0;
}
if (!f) cout << "-1\n";
else
for (int i = 1; i <= 2 * n; ++i)cout << a[i] << " \n"[i == 2 * n];
}
}
1315D. Recommendations
题意：
你有 \(n\) 本书，每本书的数量为 \(a[i]\) ，你可以花费 \(t[i]\) 让这对应的书加 \(1\) ，求总花费最小并使得 \(a[i]\) 各不相同。
利用容器 multiset
每次把同样数量的书放入一个 multiset 里，然后把最大的书拿出来保留，其他的书花费的时间加到答案里，再把 +1 之后书放进去，再反复操作。
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n; cin >> n;
vector<pair<int, int>> v(n);
for (int i = 0; i < n; ++i) cin >> v[i].first;
for (int i = 0; i < n; ++i) cin >> v[i].second;
multiset<int>ms;
sort(v.begin(), v.end());
int c = 1, i = 0;
ll s = 0, r = 0;
while (1) {
if (ms.size() == 0 && i == n) {
cout << r;
return 0;
}
if (ms.size() == 0) c = v[i].first;
for (; i < n && v[i].first == c; ++i) {
ms.insert(-v[i].second);
s += v[i].second;
}
s += *ms.begin();
ms.erase(ms.begin());
r += s, c++;
}
}