D. 预知
题目链接
题意有点绕，简单来说是其中一堆牌，问最少预知几张才能保证任取两张都不会导致种类重复。一开始对每张牌种类不是已知的，已知的是每种牌的牌数。
思路就是相当于把其中一种明牌，保证任取两张都不会导致种类重复 的 最坏情况就是预知种类最多的张数。
- n = 1 时 显然无解。
- n >= 2时 若每种牌都只有一张，则无需操作，因为怎么抽都是不同的牌。
- 若数组次大值为1，则需要执行 max - 1次， 变成第二种情况
- 否则答案就是最大值，相当于把最多牌的数量给取完，最后任取其他。
一开始尝试累加想复杂了， 这种情况应该累加 取max min 都试试 hhh。
#define ll long long
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N];
int main(){
ios::sync_with_stdio(false);
int t;cin >> t;
while(t--){
int n;
cin >> n;
bool f = 1;
for(int i = 0;i < n;i ++){
cin >> a[i];
if(a[i] != 1) f = 0;
}
if(n == 1){
cout << -1 << '\n';
continue;
}
if(f){
cout << 0 << '\n';
continue;
}
sort(a, a + n);
ll res = 0;
if(a[n - 2] == 1 && a[n - 1] != 1) res = a[n - 1] - 1;
else res = a[n - 1];
cout << res << '\n';
}
return 0;
}
E. 而后单调
题意是问是否存在从数组中选出长为m的子数组，将剩下的n-m进行排序后，将该子数组找一个位置插入后保持整个序列递增后递减
首先考虑数组不能有重复元素，因为重复无法保证严格单调，所以必然无解。
然后分成两种情况：1.严格单调递增 2.严格单调递减。
我们拿出的连续 m 个数必然是有序的，否则不符合题意。然后该段可以放进头部，中部，尾部，总结下来其实就是这段在原来的数组排序后也是一段连续的数字。
因此我们复制一下数组后排序，得到排序后的数组，并且映射一下长为m的子数组的首尾元素，此时包含符合题目条件的所有情况。 然后去原数组中寻找是否存在该子数组，并判断是否单调。这里判断单调的方法也是O1的
#define ll long long
#include <bits/stdc++.h>
using namespace std;
map <int,int> mp;
map <int,int> to;
void solve(){
int n,m;
cin >> n >> m;
vector <int> a(n+1);
mp.clear();
for(int i = 1;i <= n;i ++){
cin >> a[i];
}
for(int i = 1;i <= n;i ++){
if(mp[a[i]]){
cout << "NO" << '\n';
return ;
}
++ mp[a[i]];
}
vector <int> b(a);
sort(b.begin() + 1, b.end());
to.clear();
for(int i = 1; i + m - 1 <= n;i ++){
to[b[i]] = b[i + m -1];// 映射m段单调序列，每段（子数组）的段头元素为 b[i]和 段尾 b[i+m-1]
}
vector <int> pre(n + 5);
for(int i = 1;i <= n;i ++){
pre[i] = pre[i - 1] + (a[i] > a[i - 1]);
}
for(int i = 1;i + m - 1 <= n;i ++){
if(pre[i+m-1] - pre[i] == m-1){// 当前段满足单调序列，即m个数有m-1次单调递增
if(to[a[i]] == a[i+m-1]){ // 并且在原数组中，存在长为m的段, 和排序后的b对应
cout << "YES" << '\n';
return ;
}
}
}
//单调递减的情况同理
vector <int> suf(n + 5);
for(int i = n;i >= 1;i --){
suf[i] = suf[i+1] + (a[i] > a[i+1]);
}
for(int i = 1;i + m - 1 <= n;i ++){
if(suf[i] - suf[i+m-1] == m-1){
if(to[a[i+m-1]] == a[i]){
cout << "YES" << '\n';
return ;
}
}
}
cout << "NO" << '\n';
}
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
