Codeforces Round 922 Div2 • santisify Site

A Brick Wall ↗#

题目描述#

砖块大小为1 * k,砖块可以水平和竖直放置, 现在,我们用这样的砖块砌一堵n * m的墙, 墙的稳定性为水平砖块数与垂直砖块数之差. 问:最大稳定性是多少

解题思路#

为了使墙的稳定性最高,我们可以让所有的砖块水平放置,且砖块的大小为1*2,这样墙的稳定为 $n \times (m / 2)$

参考代码#

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
[[maybe_unused]]const int INF = 1e16 + 50, MOD = 10007;
[[maybe_unused]] typedef std::pair<int, int> pii;

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::cout << n * (m / 2) << endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--)
        solve();
    return 0;
}

cpp

B Minimize Inversions ↗#

题目描述#

长度为n的数组a和b,由于讨厌倒置( $a_{i}<a_{j},i >j$ ) 我们将调整顺序即:交换 $a_i,a_j和b_i,b_j$ 以使倒置的数较少

解题思路#

我们可以直接对一个数组排序即可,这样就可以使一个数组没有倒置,使答案最小化.

参考代码#

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
[[maybe_unused]]const int INF = 1e17 + 50;
[[maybe_unused]] typedef std::pair<int, int> pii;

void solve() {
    int n;
    std::cin >> n;
    std::vector<pii> a(n);
    for(int i = 0; i < n; i ++)
        std::cin >> a[i].first;
    for(int i = 0; i < n; i ++)
        std::cin >> a[i].second;
    std::sort(a.begin(), a.end());
    for(int i = 0 ; i < n ; i ++)
        std::cout << a[i].first << " \n"[i == n - 1];
    for(int i = 0 ; i < n ; i ++)
        std::cout << a[i].second << " \n"[i == n - 1];
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--)
        solve();
    return 0;
}

cpp