Codeforces Round 1039 (Div. 2) A-C

A. Recycling Center

题目大意

给你n个垃圾袋，每个垃圾袋有一个重量
在每秒钟，你可以选择一个垃圾袋，如果他的重量小于等于c，那么你可以不花费硬币丢掉它
当你丢掉一个垃圾袋后，其他垃圾袋在这一秒重量会翻倍
问最少花费几个硬币可以丢掉所有垃圾袋

思路

使用优先队列
从大到小存储所有垃圾袋
对于大于c的垃圾袋，无论如何都要丢掉，答案加1
对于小于c的垃圾袋，我们丢掉最大的小于等于c的垃圾袋
可以想到如果要尽可能多的丢掉小于等于c的垃圾袋，这一定是最优的

// Author: zengyz
// 2025-08-02 20:25#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{ll n, c;cin >> n >> c;vector<ll> a(n);priority_queue<ll, vector<ll>, less<ll>> pq;for (ll i = 0; i < n; i++){cin >> a[i];pq.push(a[i]);}ll ans = 0;ll now = 1;while (pq.size()){while (pq.size() && pq.top() * now > c){pq.pop();ans++;}if (pq.size() == 0)break;pq.pop();now *= 2;}cout << ans << endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}

B. Deque Process

思路

我们在奇数时间选择两端较小的一个，偶数时刻选择较大的一个，可以证明这一定是好的

证明：
考虑奇数时间
$q_i=min(p_l,p_r)$,假设最小值是$p_r$,那么$p_l>p_r$
考虑偶数时间
$q_{i+1}=max(p_l,p_{r-1})$
所以$q_{i+1}$一定大于$q_i$
同理$q_{i+2}$一定小于$q_{i+1}$

// Author: zengyz
// 2025-08-02 20:48#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++)cin >> a[i];int l = 0, r = n - 1;vector<char> ans;int now = 0;while (l <= r){if (!now){if (a[l] < a[r]){ans.push_back('L');l++;}else{ans.push_back('R');r--;}}else{if (a[l] > a[r]){ans.push_back('L');l++;}else{ans.push_back('R');r--;}}now ^= 1;}for (int i = 0; i < ans.size(); i++)cout << ans[i];cout << endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}

C. Leftmost Below

题目大意

给你一个全0的数组a
每次操作如下：
选择一个大于数组a最小值的值x
定义i为数组a中第一个小于x的值的下标，将其加x
问能否变成数组b

思路

设minn为从左到右数组b的最小值
当考虑到第i个元素时，如果$b_i\le minn$,那么我们可以直接添加$b_i$
如果$b_i>minn$ 我们可以先添加 $minn-1$ 再添加$minn$
如果大于等于两倍minn则无解

// Author: zengyz
// 2025-08-02 20:57#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n;cin >> n;vector<ll> a(n);for (int i = 0; i < n; i++){cin >> a[i];}ll maxx = a[0];bool flag = true;for (int i = 1; i < n; i++){if (2 * maxx <= a[i]){flag = false;break;}maxx = min(maxx, (ll)a[i]);}if (flag){cout << "YES" << endl;}elsecout << "NO" << endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}