Codeforces Round 872 (Div. 2) - C. LuoTianyi and the Show

Solost

2023 年 05 月 11 日

196 次浏览

暂无评论

1194字数

题目题解

## 题目链接

[链接](https://codeforces.com/contest/1825/problem/C)

## 题目大意

题目的意思是有n个人，m个座位，每个人有三种座位坐法

1. 如果是-1代表坐在最左边人的左边，如果还没有人坐，那就坐在最右边m位置
2. 如果是-2代表坐在最右边人的右边，如果还没有人坐，那就坐在最左边1位置
3. 坐在x位置

然后给你一个数列长度为n，a[i]只有x,-1,-2这两种，问你最多能坐多少个人

## 题解

我们不妨来换个思路，x位置的人只能坐在x位置，但是-1,-2可以按照要求坐座位，一个人有多种坐法，总体思路就是固定座位的人坐在那个位置，然后来按照要求填写-1，-2的人。特例情况就是先放-1，-2的情况分别讨论以下就行了

## 代码

```cpp
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int s[N];
void solve()
{
    int n, m;
    cin >> n >> m;
    map<int, int> a;
    memset(s, 0, sizeof s);
    set<int> q;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(x > 0){
            s[x] = 1;
            q.insert(x);
        }
        a[x]++;
    }
    for(int i = 1; i <= m; i++){
        s[i] += s[i - 1];
    }
    int ans = 0;
    if(a[-1]){
        ans = max(ans, min(m, s[m - 1] + a[-1]));
        // cout << ans << endl;
    }
    if(a[-2]){
        ans = max(ans, min(m, s[m] - s[1] + a[-2]));
        // cout << ans << endl;
    }
    for(auto x : q){
        ans = max(ans, 1 + min(x - 1, s[x - 1] + a[-1]) + min(m - x, s[m] - s[x] + a[-2]));
    }
    cout << ans << endl;
}
int main()
{
    IOS;
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 05 月 11 日