A
题意
给你一个循环的数列,你可以进行以下操作,选择相邻两个中的一个删除,求最少操作次数,使得数列中的所有元素相等。
方法
直接求最大的个数相等的数目maxn
,输出n-maxn
即可。
代码
#include<bits/stdc++.h> using namespace std; using ll=long long; void solve() { int n; cin>>n; std::vector<int> a(n,0); map<int,int> mp; for(auto &t: a) { cin>>t; mp[t]++; } int maxn=0; for(auto [x,y]: mp) { maxn=max(maxn,y); } cout<<n-maxn<<"\n"; } int main() { int t=1; cin>>t; while(t--) solve(); return 0; }
|
B
题意
看题目吧。
方法
构造。直接按照交错构造即可。
偶数的全排列无法构造。
代码
#include<bits/stdc++.h> using namespace std; using ll=long long; void solve() { int n; cin>>n; if(n%2==0) cout<<-1<<"\n"; else { for(int i=n;i>0;i-=2) cout<<i<<" "; for(int i=2;i<n;i+=2) cout<<i<<" \n"; cout<<"\n"; } } int main() { int t=1; cin>>t; while(t--) solve(); return 0; }
|
D
题意
给你一个数列,你需要选出其中的一个子序列(不能有重复元素),要求你需要找到最小的全排列。
方法
不难发现:我们可以只需要让奇数位大,偶数位小即可。
这里可以先找每一个数字出现的最晚位置,存入
一个vector
中,后面再贪心地不断往前进行添加,然后再删去即可。
这里可以用双指针进行维护一个区间[l,r]
,维护的想法可以参考一下Z
函数的实现。
代码
#include<bits/stdc++.h> using namespace std; using ll=long long; void solve() { int n; cin>>n; std::vector<int> a(n,0); for(int i=0;i<n;i++) cin>>a[i]; std::vector<int> book(n+1,-1); std::vector<pair<int,int>> b; for(int i=n-1;i>=0;i--) { if(book[a[i]]==-1) { b.push_back({i,a[i]}); book[a[i]]=i; } } sort(b.begin(),b.end());
book.assign(n+1,0); std::map<int, int> map; int ptr1=0,ptr2=0,cur=0; std::vector<int> ans; while(ptr2<b.size()) { auto [id,val]=b[ptr2]; for(cur;cur<=id;cur++) { if(book[a[cur]]==0) { map[a[cur]]++; } } if(book[val]) { ptr2++; continue; } while(book[val]==0) { int tmp=0; if(ans.size()%2==0) { tmp=map.rbegin()->first; } else { tmp=map.begin()->first; } book[tmp]=1; ans.push_back(tmp); map.erase(tmp);
for(ptr1;a[ptr1]!=tmp;ptr1++) { if(map.count(a[ptr1])) { map[a[ptr1]]--; if(map[a[ptr1]]==0) map.erase(a[ptr1]); } } } ptr2++; } cout<<ans.size()<<"\n"; for(int i=0;i<ans.size();i++) { cout<<ans[i]<<" \n"[i==ans.size()-1]; } } int main() { int t=1; cin>>t; while(t--) solve(); return 0; }
|