CF-1173-C Nauuo and Cards(贪心+模拟)

题目链接

https://codeforces.com/contest/1173/problem/C

题目大意

有n张牌标号1到n,还有n张牌为0,它们混在一起,现在告诉你你手上有哪n张牌,堆里自顶到底有哪n张牌,现在你只能选择一张手中的牌放到堆底并把堆顶的拿走,问最少多少次操作可以让堆自顶到底递增排列。

解题思路

我们可以发现要不就是序列中已经有一些从一开始且有序的后缀且可以继续往后放最后一个元素+1的牌,这样就直接可以构造。否则的话要看1后面的,比如堆中本来是1 3 2,这样在需要2的时候你却拿不到它,因此要等2一秒,因此要计算max(ans, i – yi – a[i] + 1)。结果就是1要等的时间,加上把1拿出来所需的时间和把n个数都放进去的时间就是答案了,两种答案取min即可。

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;
int a[2 * maxn], b[2 * maxn];

int main() {
    int n;
    cin >> n;
    int d, yi = 0;
    for (int i = 0; i < n; i++) {
        cin >> d;
        b[i] = d;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == 1)
            yi = i;
    }
    int ans = 0, aans;
    multiset<int> p;
    for (int i = 0; i < n; i++) {
        if (b[i])
            p.insert(b[i]);
    }
    int now = 1;
    while (p.size() && ans < n) {
        a[n + now] = *p.begin();
        p.erase(p.begin());
        if (a[now])p.insert(a[now]);
        now++;
        ans++;
    }
    for (int i = 1; i <= n; i++) {
        if (a[now + i - 1] != i)
            ans = 0x3f3f3f3f;
    }
    aans = ans;
    ans = 0;
    for (int i = yi + 1; i <= n; i++) {
        if (a[i] != 0) {
            ans = max(ans, i - yi - a[i] + 1);
        }
    }
    ans += yi + n;
    cout << min(aans, ans) << endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注