当前位置：首页 > ds >正文

cf1703G

ds 2025/8/27 15:58:46

原题链接：https://codeforces.com/contest/1703/problem/G

题目背景：

n 个箱子，n 把钥匙，每个箱子内都有 ai 金币，每次可以使用好钥匙或者坏钥匙，好钥匙需花费 k 金币，坏钥匙不需要花费金币但是它及它以后的箱子的收益都会减半。

思路：

可以证明先使用好钥匙总是比先使用坏钥匙更优，既假设有两个箱子的收益为 x,y，我们先使用好钥匙再使用坏钥匙的收益为 $x - k + \left \lfloor \frac{y}{2} \right \rfloor$ ，先使用坏钥匙再使用好钥匙的收益为 $\left \lfloor \frac{x}{2} \right \rfloor + \left \lfloor \frac{y}{2} \right \rfloor - k$ ，可看出使用好钥匙是更优的。所有我们可以前 i 个使用好钥匙，后 n - i 个使用坏钥匙，由于 ai 是 int 范围内的，所以我们坏钥匙只需循环 log(n - i)个，这样时间复杂度为O(nlogn)。

数据范围：

n 总和不超过 1e5。

时间复杂度：

O(nlogn)。

ac代码：

#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}void solve()
{int n, k;cin >> n >> k;vi a(n + 10);vector<ll> s(n + 10, 0);for (int i = 1; i <= n; ++i){cin >> a[i];s[i] = a[i] + s[i - 1];}ll ans = 0;for (int i = 0; i <= n; ++i) // 使用n次好钥匙{ll cnt = s[i] - (ll)i * k;for (int j = i + 1; j <= min(n, i + 31); ++j){cnt += a[j] >> (j - i);}ans = max(ans, cnt);}cout << ans << endl;
}int main()
{ioscc;int T;cin >> T;while (T--)solve();return 0;
}

查看全文

http://www.xdnf.cn/news/9420.html