题目链接
题目大意
题目的意思是有n个人,m个座位,每个人有三种座位坐法
- 如果是-1代表坐在最左边人的左边,如果还没有人坐,那就坐在最右边m位置
- 如果是-2代表坐在最右边人的右边,如果还没有人坐,那就坐在最左边1位置
- 坐在x位置
然后给你一个数列长度为n,a[i]只有x,-1,-2这两种,问你最多能坐多少个人
题解
我们不妨来换个思路,x位置的人只能坐在x位置,但是-1,-2可以按照要求坐座位,一个人有多种坐法,总体思路就是固定座位的人坐在那个位置,然后来按照要求填写-1,-2的人。特例情况就是先放-1,-2的情况分别讨论以下就行了
代码
#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;
}