Codeforces Round 961 (Div. 2)

A

目标是将所有 k 个棋子放置在棋盘上，使得占据的对角线的数量最少。

易得最大对角线一条，长度为n，之后的对角线长度一次减一，且相同长度的对角线有两条。

#include <iostream>
using namespace std;


void solve()
{
    int m,n;
    int cnt = 0;
    cin >> m >> n;
    if(n == 0)
    {
         cout << cnt << endl;
         return;
    }
    cnt+= 1;
    n -=m;
    m--;
    int flag = 0;
    while(1)
    {
        if(n <= 0)  break;
        if(flag == 2)    
        {
            flag = 0;
            m--;
        }
        else
        {
            flag++;
            cnt++;
            n -= m;
        }
    }
    cout << cnt << endl;
}


int main()
{
   int n;
   cin >> n;
   while(n--)
    {
        solve();
    }
}

B1

有一个花店，提供了 n 朵花，每朵花的花瓣数不同。每朵花的价格等于它的花瓣数。
一个女孩想要为她的生日购买一个花束。她的目标是使花束的总花瓣数尽可能多。
她有 m 枚硬币作为预算。
花束中所有花的花瓣数之间的差值不能超过1。例如，花瓣数为3和4的花可以在同一个花束中，但是花瓣数为1和3的花不能在同一个花束中。
总花瓣数最大化的前提下，花束的总价格不能超过 mmm 枚硬币。

这题比赛没做出来，没考虑到一些特殊情况，下面是黄神的题解，可以理解为采用了滑动窗口：

#include <iostream>  
#include <vector>  
#include <algorithm> 
 
using namespace std;
 
int main() {
  int t;
  cin >> t; 
 
  while (t--) {
    long long n, m;
    cin >> n >> m; 
 
    vector<long long> flowers(n);
    for (int i = 0; i < n; ++i) {
      cin >> flowers[i]; 
    }
 
    sort(flowers.begin(), flowers.end());
 
    long long max_petals = 0;  
    long long num = 0;//记录当前的花瓣数
    long long cost = 0;//当前的花销
    //前i朵中选j个；
    for (int i = 0,j = 0; i < n; i++)
    {
      num += flowers[i];
      cost += flowers[i];
      while (j <= i&&(cost>m||(flowers[i]-flowers[j])>1))
      {
        cost -= flowers[j];
        num -= flowers[j];
        //第j朵就不要了
        j++;
      }
      max_petals = max(max_petals, cost);
    }
 
 
 
    cout << max_petals << endl;
  }
 
  return 0;
}

jiangly的题解，只能说不愧是jiangly，用上了很多cpp特性，从这里的边界处理学到了许多。特别是max和min的应用。

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

#define ll long long

const int N = 2e5+10;


void solve()
{
    int n;
    ll m;
    ll ans = 0;
    cin >> n >> m;
    map<int, int>   mp;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        mp[x]++;
    }
    for (auto &[x, y] : mp) //遍历map元素
    {
      ans = max(ans, 1LL * x * min<ll>(y, m/x));    //能容纳的最大值
      if(mp.find(x + 1) != mp.end())
      {
            int z = mp[x + 1];      //取下一元素
             for (int i = 1; i <= y && 1LL * i * x <= m; i++) {     //尝试将此节点与下一节点组合
                ans = std::max(ans, 1LL * i * x + 1LL * (x + 1) * std::min<ll>(z, (m - 1LL * i * x) / (x + 1)));
            }
      }
    }
    cout << ans << endl;


}



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t ;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

B2

一个女孩为她的生日准备一个花束。花店里有 n 种不同类型的花，每种花的花瓣数和数量都被给出。每朵花的价格等于它的花瓣数。女孩希望组成一个花束，使得花束中的所有花的花瓣数之差不超过1，并且总花瓣数尽可能大。她有 m 枚硬币作为预算，不能超过这个预算。

这里的话，我们需要遍历每种花。

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;

#define ll long long

const int N = 2e5+10;


void solve()
{
 int n;
    ll 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;
    }
    
    ll ans = 0;
    for (auto [x, y] : f) {
        // 计算仅用花瓣数为 x 的花时的最大花瓣数
        ans = std::max(ans, 1LL * x * std::min<ll>(y, m / x));      
        
        if (f.find(x + 1) != f.end()) {     //元素按照升序遍历。
            int z = f[x + 1];
            ll c;
             // 如果花瓣数为 x 的花可以完全使用预算
            if (1LL * x * y >= m) {
                
                c = m / x;      //可以拿的第y种花的最大数
            } else {
                   // 计算最多能用多少花瓣数为 x + 1 的花
                c = y + std::min<ll>(z, (m - 1LL * x * y) / (x + 1));
            }
            ans = std::max(ans, std::min(m, c * x + std::min<ll>(c, z)));
        }
    }
    std::cout << ans << "\n";
}



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t ;
    cin >> t;
    while (t--)
        solve();

    return 0;
}