A - 对角线
分析
模拟 遍历题意中所说的 $n$ 条对角线，除了反对角线其余均是遍历两次。
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int t,n,k;
void solve()
{
int ans=0;
cin>>n>>k;
for(int i=n;i>=1;i--)
for(int j=1;j<=(i==n?1:2);j++)
{
if(k>0)
{
ans++;
k-=i;
}
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>t;
while(t--)solve();
return 0;
}
B1 - 花束
分析
暴力 做的时候用双指针和前缀和，但是似乎这个想法不对（谁能看一下，求调）
错解
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+10;
int t,n,m,a[N],s[N],l,r;
//在花瓣差<=1的情况下&&钱够的情况下 最多有多少花瓣
//双指针忘了
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
//cout<<s[n-1];
int maxn=0;
for(int i=1,j;i<=n;i++)
{
j=i+1;
while(a[j]-a[i]<=1&&a[j]-a[i]>=0)j++;
l=i,r=j-1;
//cout<<l<<' '<<r<<' ';
while(s[r]-s[l-1]>m)l++;
maxn=max(maxn,s[r]-s[l-1]);
//cout<<l<<' '<<r<<endl;
//for(int k=l;k<=r;k++)cout<<a[i]<<' ';
//cout<<maxn<<endl;
// break;
}
cout<<maxn<<endl;
//cout<<l<<' '<<r<<endl;
}
//map中contains是否存在,count是获取大于等于的元素
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>t;
while(t--)solve();
return 0;
}
正解是去暴力出x和x+1，以后长记性了，凡是这种相邻差相邻模的，一般是在选一个数的基础上，看直接构造这个数最符合的情况看是否存在对于 map 的 count 操作熟练使用。
首先，统计花瓣数为 $x$ 的花朵总数 $c_{x}$ （使用 map ，即 $(x, c_{x})$ ，其中 $c_{x}$ 是元素等于 $x$ 的数量）。
显然，每 $x$ 朵花所需的花瓣数不会超过 $\left\lfloor\frac{m}{x}\right\rfloor$ 朵，以确保花瓣总数不会超过 $m$ 。
然后我们遍历所有的 $x$ ，假设都有 $x + 1$ 个花瓣和 $x$ 个花瓣组合为花束。对于$x$ 片花瓣的，其数量在 $0 \le cnt1 \le min(c_{x}, \left\lfloor\frac{m}{x}\right\rfloor)$ 间，这样已有 $cnt1 * x$ 片花瓣。还有 $m - cnt1 * x$ 枚硬币可来购买 $x + 1$ 个花瓣的花朵。最多可以买到 $cnt2 = min(c_{x + 1}, \left\lfloor\frac{m - cnt1 * x}{x + 1}\right\rfloor)$ 朵花瓣数为 $x + 1$ 的花。于是一直对 $cnt1 * x + cnt2 * (x + 1)$ 求最值即可。
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=1e5+10;
int n,m,x;
void solve()
{
int ans=0;
cin>>n>>m;
map<int,int>mp;
for(int i=0;i<n;i++)
{
cin>>x;
mp[x]++;
}
for(auto &w:mp)
{
ans=max(ans,w.x*min(w.y,m/w.x));
if(mp.count(w.x+1))
{
int z=mp[w.x+1];
for(int i=1;i<=w.y&&i*w.x<=m;i++)
{
ans=max(ans,i*w.x+(w.x+1)*min(z,(m-i*w.x)/(w.x+1)));
}
}
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}
B2 - 花束（困难版）
我们已经有一个包含 $c_x$ 的列表。我们可以使用哈希映射来检查 $x$ 中是否有 $c_x$ 。
我们将再次尝试只用带有 $x, x + 1$ 花瓣的花朵来组合花束。我们设为 $k1 = min(c_{x}, \left\lfloor\frac{m}{x}\right\rfloor)$ 。然后得到 $coins = m - k1 * x$ 。再设 $k2 = min(c_{x + 1}, \left\lfloor\frac{coins}{x + 1}\right\rfloor)$ 。然后得到 $coins = m - (k1 * x + k2 * (x + 1))$ 。让我们尽可能多次地将花瓣数为 $x$ 的花朵替换为花瓣数为 $x + 1$ 的花朵。这样可以做 $r = min(k1, c_{x + 1} - k2, coins)$ 次，因为每次操作需要 1 枚硬币、1 朵花束中有 $x$ 个花瓣的花和 1 朵花束中没有 $x + 1$ 个花瓣的花。我们总共可以得到 $(k1 - r) * x + (k2 + r) * (x + 1)$ 朵花瓣。
这种组合方式是最佳的。原因如下。假设我们有 $0 \le b1 \le c_{x}$ 朵花，花瓣数为 $x$ ， $0 \le b2 \le c_{x + 1}$ 朵花，花瓣数为 $x + 1$ ，总值为 $b1 * x + b2 * (x + 1)$ 。我们已经知道， $b1 \le k1$ 是通过选择 $k1$ 得到的。如果是 $k1 - r < b1$ ，那么我们可以 “撤销 “我们的操作 $r + b1 - k1$ 次，总和仍然不大于 $m$ ，而且我们知道现在有 $x + 1$ 个花瓣的花不可能超过 $k2 + r + b1 - k1$ 朵，否则我们就没有选择最佳的 $k2$ .如果是 $k2 + r < b2$ ，那么就是 $r \ne c_{x + 1} - k2$ ；如果是 $r = k1$ ，那么就是只有 $x + 1$ 朵花瓣的情况，也就是 $x + 1, x + 2$ ；如果是 $r = coins$ ，那么就是 $m = (k1 - r) * x + (k2 + r) * (x + 1)$ ，我们已经找到了最大值。因此， $b2 \le k2 + r$ 和 $b1 \le k1 - r$ 以及 $b1 * x + b2 * (x + 1)$ 都不优于最优值。
总时间复杂度为 $O(n)$ 。
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
void solve() {
ll n, m;
cin >> n >> m;
vector<ll> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<ll> cnt(n);
for (int i = 0; i < n; i++) {
cin >> cnt[i];
}
vector<pair<ll, ll>> v(n);
for (int i = 0; i < n; i++) {
v[i] = {a[i], cnt[i]};
}
sort(v.begin(), v.end());
ll res = 0;
ll px = -1, pc = 0;
for (auto& now: v) {
ll x = now.first, c = now.second;
// only
ll l = 0, r = c;
while (l < r) {
ll mid = (l + r + 1) >> 1;
if (mid * x <= m) l = mid;
else r = mid - 1;
}
if(r * x <= m) res = max(res, r * x);
// between
if (x == px + 1) {
if (m >= x * c + px * pc) {
res = max(res, x * c + px * pc);
} else if (m >= px * pc) {
ll t = m - px * pc;
ll s = px * pc;
ll cbig = min(t / x, c);
s += x * cbig;
s += min({t - x * cbig, pc, c - cbig});
res = max(res, s);
} else {
ll csmall = min(m / px, pc);
ll s = px * csmall;
s += min({m - px * csmall, csmall, c});
res = max(res, s);
}
}
px = x;
pc = c;
}
cout << res << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T--) solve();
return 0;
}
#include <bits/stdc++.h>
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
void solve() {
int n;
i64 m;
std::cin >> n >> m;
std::map<int, int> f;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
for (int i = 0; i < n; i++) {
int c;
std::cin >> c;
f[a[i]] = c;
}
i64 ans = 0;
for (auto [x, y] : f) {
ans = std::max(ans, 1LL * x * std::min<i64>(y, m / x));
if (f.contains(x + 1)) {
int z = f[x + 1];
i64 c;
if (1LL * x * y >= m) {
c = m / x;
} else {
c = y + std::min<i64>(z, (m - 1LL * x * y) / (x + 1));
}
ans = std::max(ans, std::min(m, c * x + std::min<i64>(c, z)));
}
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T;
std::cin >> T;
while (T--) {
solve();
}
return 0;
}
