1945(div3)
A. Setting up Camp
组委会计划在游览结束后带领奥林匹克运动会的参赛选手进行徒步旅行。目前,正在计算需要搭乘的帐篷数量。据了解,每个帐篷最多可容纳
在参赛选手中,有
- 每个内向的人都想独自住在帐篷里。因此,内向者的帐篷里必须只有一个人--只有内向者自己。
- 每个外向者都希望与另外两个人住在一个帐篷里。因此,一个外向者的帐篷里必须正好有三个人。
- 每个人都可以选择任何一种方式(独居、与他人同住或与他人同住)。
组委会非常尊重每位参赛者的意愿,因此他们希望满足所有参赛者的愿望。
请告诉我们至少需要多少顶帐篷,以便所有参加者都能根据自己的喜好找到住处。如果无法满足所有参与者的愿望,则输出
void solve() {
int a, b, c;cin >> a >> b >> c;
int x = b % 3;
if (x && x + c < 3) {
cout << "-1\n";return;
}
cout << a + (b + c) / 3 + ((b + c) % 3 ? 1 : 0) << '\n';
}
B. Fireworks
徒步旅行的其中一天恰逢节假日,因此决定晚上在营地安排一场节日焰火表演。为此,徒步旅行的组织者购买了两个烟花发射装置和大量的发射炮弹。
两个装置同时开启。第一个装置每隔
每个烟花在发射后的
天空中最多可以同时看到多少枚烟花?
#define int long long
void solve() {
int a, b, m;cin >> a >> b >> m;
cout << m / a + m / b + 2 << '\n';
}
C. Left and Right Houses
莱托沃村有
道路将从两栋房子之间穿过。它左边的房子将被宣布为左侧,右边的房子将被宣布为右侧。更正式地说,让道路从房屋
为了使设计公平,我们决定在铺设道路时,至少要让村子两边各一半的居民对选择感到满意。也就是说,在一侧的
在路的左边,会有
确定道路应该铺设在哪座房子
如果有多个合适位置
主要是对于找到最合适的答案的问题,当 n 为偶数时没有问题,当 n 为奇数时就会有两个可能答案取最小值
void solve() {
int n;cin >> n;string a;cin >> a;a = ' ' + a;
vector<int> pre(n + 1), suf(n + 2);
for (int i = 1;i <= n;i++) {
pre[i] = pre[i - 1] + (a[i] == '0');
}
for (int i = n;i >= 1;i--) {
suf[i] = suf[i + 1] + (a[i] == '1');
}
vector<int> ans;
for (int i = 0;i <= n;i++) {
int x = pre[i], y = suf[i + 1];
if (x >= (i + 1) / 2 && y >= (n - i + 1) / 2) {
ans.push_back(i);
}
}
int op1 = (n + 1) / 2, op2 = n / 2, res = 1e9, tar = 1e9;
for (int i = ans.size() - 1;i >= 0;i--) {
if (abs(op1 - ans[i]) < res || abs(op2 - ans[i]) < res) {
res = min(abs(op1 - ans[i]), abs(op2 - ans[i]));
tar = ans[i];
}
if (abs(op1 - ans[i]) == res || abs(op2 - ans[i]) == res) {
res = min(abs(op1 - ans[i]), abs(op2 - ans[i]));
tar = min(tar, ans[i]);
}
}
cout << tar << '\n';
}
D. Seraphim the Owl
大家排成
对于队列中的
基里尔很节俭,所以他想花尽可能少的硬币,但是他又不想等太久,所以基里尔认为他应该排在第一个
请帮助基里尔确定,为了不等太久,他最少需要花费多少金币。
可以注意到确定的答案序列一定有一个特点,最后一个值一定是在
void solve() {
int n, m;cin >> n >> m;
vector<int> a(n + 1), b(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
for (int i = 1;i <= n;i++)cin >> b[i];
ll ans = 1e18, now = 0;
for (int i = n;i >= 1;i--) {
if (i <= m)ans = min(ans, now + a[i]);
now += min(a[i], b[i]);
}
cout << ans << '\n';
}
E. Binary Search
给你一个大小为
你忘了二进制搜索必须对数组进行排序。
为了得到正确的答案,你可以在运行算法之前执行以下操作不超过
执行二进制搜索声明两个变量
- 如果
,结束循环 - 如果
,赋值 ,否则 。
我们的目标是在算法之前重新排列排列组合中的数字,以便在算法执行之后,
Solution
问题在于如何在操作数不超过两个的情况下,使得二分结果恰好为
这样可以将数组排序,这样一定能达到目标,但是很容易超过 2 的答案。
vector<pair<int, int>> op;
for (int i = 1;i <= n;i++) {
if (a[i] != i) {
op.push_back({i,mp[i]});
mp[a[i]] = mp[i];
swap(a[i], a[mp[i]]);
mp[i] = i;
}
}
cout << op.size() << '\n';
for (auto [x, y] : op)cout << x << " " << y << '\n';
实际上,被骗了,实际上,很简单,只需要一次一定能解决问题。
只需要在二分最终结果
void solve() {
int n, x;cin >> n >> x;vector<int> a(n + 1);
int p = 0;
for (int i = 1;i <= n;i++) {
cin >> a[i];
if (a[i] == x)p = i;
}
int l = 1, r = n + 1;
while (r - l > 1) {
int m = r + l >> 1;
if (a[m] <= x)l = m;
else r = m;
}
cout << "1\n";
cout << p << " " << l << '\n';
}
F. Kirill and Mushrooms
橡树下生长着
灵药的强度等于其中蘑菇的数量与这些蘑菇中最小魔力的乘积。为了配制灵药,基里尔将依次采摘生长在橡树下的蘑菇。基里尔可以按照任何顺序采集蘑菇。
然而,事情并非如此简单。智慧橡树告诉基里尔从
你的任务就是帮助基里尔采集蘑菇,使他能够酿造出最大魔力的灵药。不过,基里尔有点害怕在橡树附近逗留太久,所以在所有合适的采集蘑菇的选项中,他要求您找到蘑菇数量最少的那个。
Solution
堆
(待更
Codeforces Round 935 (Div. 3)(A,B,C,D,E,F)-CSDN博客
void solve() {
int n;cin >> n;
vector<int> t(n + 1), a(n + 1);
for (int i = 1;i <= n;i++)cin >> t[i];
for (int i = 1, id;i <= n;i++) {
cin >> id;
a[i] = t[id];
}
priority_queue <int, vector<int>, greater<int>> h;
ll ans = 0, tot;
for (int i = n;i >= 1;i--) {
h.push(a[i]);
if (n - i + 1 < i)continue;
while (h.size() > i)h.pop();
if (ans <= 1ll * i * h.top()) {
ans = 1ll * i * h.top();
tot = h.size();
}
}
cout << ans << ' ' << tot << '\n';
}