首页 > 其他 > 详细

Codeforces Global Round 9 C. Element Extermination

时间:2020-07-07 00:11:28      阅读:62      评论:0      收藏:0      [点我收藏+]

题目链接:https://codeforces.com/contest/1375/problem/C

题意

给出一个大小为 $n$ 的排列 $a$,如果 $a_i < a_{i+1}$,则可以选择移去二者之一,判断排列最终能否只剩一个数。

题解一

考虑小于 $a_0$ 的所有的数,如果这些数都可以移去,那么剩余的数都大于 $a_0$,显然也都可以移去。

所以可以记录大于 $a_0$ 的每个数的位置,然后标记它们左端可以移除的数,最后判断小于 $a_0$ 的数是否都能移除即可。 

代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    int a[n] = {};
    int pos[n] = {};
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        --a[i];
        pos[a[i]] = i;
    }
    bool can_remove[n] = {};
    bool vis[n] = {};
    for (int i = n - 1; i > a[0]; i--) {
        for (int j = pos[i] - 1; j >= 0 and !vis[j]; j--) {
            can_remove[a[j]] = true;
            vis[j] = true;
        }
    }
    bool ok = true;
    for (int i = 0; i < a[0]; i++)
        if (!can_remove[i]) ok = false;
    cout << (ok ? "YES" : "NO") << "\n";
}

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

题解二

一个小于 $a_0$ 的数只有在最右端的时不能移除,所以判断 $a_0 < a_{n - 1}$ 即可。

代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    int a[n] = {};
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cout << (a[0] < a[n - 1] ? "YES" : "NO") << "\n";
}

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

 

Codeforces Global Round 9 C. Element Extermination

原文:https://www.cnblogs.com/Kanoon/p/13258153.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!