Codeforces Round 922 (Div. 2)

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;
}

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;
}