ABC 379 题解

目录

• ABC 379 题解
• 目录
• A Cyclic
• B Strawberries
• C Sowing Stones
• D Home Garden
• E Sum of All Substrings

A Cyclic

man
what can i say?

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

void sol()
{
    string s;
    cin >> s;
    cout << s[1] << s[2] << s[0] << ' ' << s[2] << s[0] << s[1];
}
int main()
{
    sol();
    return 0;
}

B Strawberries

贪心，把每一段O的个数/k加起来就行了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

void sol()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int cnt = 0, ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == 'O')
            ++cnt;
        else
        {
            ans += cnt / k;
            cnt = 0;
        }
    }
    ans += cnt / k;
    cout << ans << endl;
}
int main()
{

    sol();
    return 0;
}

C Sowing Stones

每个ai如果有石子，只能往前移动，最终状态是1~N 只能有一颗。
求最少的移动代价。

可以分成两部分：

1. 判断条件是否合法
   这个比较简单，石子数量总和是n，并且前缀和都要大于等于每一位置。

2. 求解min移动代价
   可以先假设石子全在1，算出最大代价，然后减掉帮你移动好的石子的代价

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
struct dot
{
    ll x, c;
};

bool cmp(dot a, dot b)
{
    return a.x < b.x;
}
void sol()
{
    ll n, m;
    cin >> n >> m;
    vector<dot> arr(m + 1);
    ll sum = 0;

    for (int i = 1; i <= m; i++)
        cin >> arr[i].x;

    for (int i = 1; i <= m; i++)
    {
        cin >> arr[i].c;
        sum += arr[i].c;
    }

    // 判断是否合法
    if (sum != n)
    {
        cout << -1 << endl;
        return;
    }
    sort(arr.begin() + 1, arr.end(), cmp);
    // 计算前缀和
    ll now_tot = 0;
    for (int i = 1; i <= m; i++)
    {
        if (now_tot < arr[i].x - 1) // 如果出现前缀和小于x-1，说明前面的石子覆盖不到x-1
        {
            cout << -1 << endl;
            return;
        }
        now_tot += arr[i].c;
    }
    // 计算
    ll ans = n * (0 + n - 1) / 2; // 假设n个石子都在1位置,代价就是0+1+2+3+...+n-1
    for (int i = 1; i <= m; i++)
        ans -= (arr[i].x - 1) * arr[i].c; // 减去实际位置*石子数量

    cout << ans << endl;
}
int main()
{
    sol();
    return 0;
}

D Home Garden

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

void sol()
{
    ll q;
    cin >> q;
    ll x, m;
    ll time = 0;//当前时间
    priority_queue<ll, vector<ll>, greater<ll>> pq;//min heap，显然我们要先收获最早种下的,其实用普通队列也行
    while (q--)
    {
        cin >> x;
        if (x != 1)
        {
            cin >> m;
            if (x == 2)
                time += m;//时间增加
            else
            {
                ll ans = 0;
                while (!pq.empty() && time - pq.top() >= m)//如果当前时间离种下的时间已经不小于m
                {
                    ++ans;//可以收获了喵
                    pq.pop();
                }
                cout << ans << '\n';
            }
        }
        else
            pq.push(time);//种下的时间
    }
}
int main()
{
    sol();
    return 0;
}

E Sum of All Substrings

在补了在补了