牛客练习赛114题解
C.Kevin的彩蛋
-
比赛的时候读错题了,题目求的是一个长为m的排列,所以只要a数组中包含有
的元素,那么就一定是有解的。
-
那这就启发我们每次都去找一个最长的排列,这样就会使拿的次数最少,对于
每一个数字记录他的下标,然后找从1最长可以扩展到哪里,如果为k,再找从k+1最长可以扩展到哪里。
-
按照这样子去选的话每一个排列之间一定是独立的,例如对于3,2,4这样的序列,你选3次才可以选齐。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int a[N];
void solve() {
int n, m; cin >> n >> m;
vector<int> e[m + 2];
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] <= m) e[a[i]].push_back(i);
}
for (int i = 1; i <= m; i++) {
if (e[i].empty()) {
cout << "-1\n";
return ;
}
}
int ans = 0, k = 1;
for (int i = 1; i <= m;) {
int ma = 0;
for (int j : e[i]) {
int s = j;
int tt = k;
while (s < n && a[s] == tt) s ++, tt ++;
tt --;
ma = max(ma, tt);
}
ans ++, i = ma + 1, k = ma + 1;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
cin >> T;
while (T--){
solve();
}
return 0;
}
D.长途的春天
- 贪心的去选择最长的顺子,最终看能不能把所有的牌都选完,选的时候需要进行判断,比如 5 5 6 6你选了5就可以继续选6,而 5 5 6 7你就只能选一次5,否则你会抢走其他顺子的牌。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
int a[200010], cnt[200010];
void solve() {
memset(cnt, 0, sizeof cnt);
int n; cin >> n;
if (n < 4) {
cout << "NO\n";
return ;
}
set<int> s;
for (int i = 0; i < n; i++) {
cin >> a[i];
cnt[a[i]] += 1;
s.insert(a[i]);
}
int t = 0;
while (true) {
int x = *s.begin();
int cur = 0;
while (cnt[x] > 0) {
cnt[x] --;
cur ++;
if (!cnt[x]) s.erase(x);
// 如上面所说
if (cnt[x + 1] < cnt[x] + 1) break;
x ++;
}
if (cur < 5)
break;
t += cur;
}
if (t == n) cout << "YES\n";
else cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T = 1;
cin >> T;
while (T--){
solve();
}
return 0;
}