codeforce每日一题链接
题目链接
题目描述
给你一个数组,请你在必须翻转且只能翻转一次的基础上找到字典序最大的数组,翻转规则为:假设翻转区间为[l, r],那么先使得a[l, r] = a[r, l],在调换a[1, l-1]和a[r+1, n]的顺序。
样例
输出样例1
9
5
2 3 1 5 4
9
4 1 6 7 2 8 5 3 9
4
4 3 2 1
2
2 1
6
3 2 4 1 5 6
7
3 2 1 5 7 6 4
10
10 2 5 6 1 9 3 8 4 7
4
4 2 1 3
1
1
输入样例1
5 4 1 3 2
9 4 1 6 7 2 8 5 3
3 2 1 4
1 2
6 5 3 2 4 1
7 6 4 5 3 2 1
9 3 8 4 7 1 10 2 5 6
3 4 2 1
1
算法1
(暴力枚举) $O(n^2)$
这道题的数据量只有$1000$,所以直接暴力也是可以的。我们可以分类讨论,如果n是1的话,直接输出就好了;否则就找最大值,如果最大值在第一个,就找次大值,假设最大值或者次大值的下标为$idx$,之后就可以暴力枚举了,从idx前开始枚举翻转到哪里,枚举翻转区间为$[i, idx]$,动态维护字典序最大的解,最后在比较一下翻转$[idx, n]$。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int w[N];
int find(int x)
{
for(int i=1;i<=n;i++)
if(w[i]==x) return i;
return 0;
}
bool cmp(vector<int> &str1, vector<int> &str2, vector<int> &str)
{
vector<int> tmp;
for(auto u:str2) tmp.pd(u);
for(auto u:str1) tmp.pd(u);
for(int i=0;i<str.size();i++){
if(str[i]>tmp[i]) return false;
else if(str[i]<tmp[i]) return true;
}
return false;
}
inline void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
if(n==1) cout<<w[1]<<endl;
else{
int idx = find(n);
if(idx==1){
idx = find(n-1);
}
vector<int> str1, str2, str;
for(int i=1;i<idx;i++) str1.pd(w[i]), str.pd(0);
for(int i=idx-1;i;i--){
str2.pd(str1[str1.size()-1]);
str1.erase(str1.begin()+str1.size()-1);
if(cmp(str1, str2, str)){
str.clear();
for(auto u:str2) str.pd(u);
for(auto u:str1) str.pd(u);
}
}
vector<int> res;
for(int i=idx;i<=n;i++) res.pd(w[i]);
for(auto u:str) res.pd(u);
vector<int> tmp;
for(int i=n;i>=idx;i--) tmp.pd(w[i]);
for(int i=1;i<idx;i++) tmp.pd(w[i]);
for(int i=0;i<n;i++){
if(tmp[i]>res[i]){
res.clear();
for(auto u:tmp) res.pd(u);
break;
}else if(tmp[i]<res[i]) break;
}
for(int i=0;i<n;i++) cout<<res[i]<<" ";
cout<<endl;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
算法2
(技巧) $O(n)$
在上面解的基础上,我们只需要判断现在枚举到的$w[i]$和$w[1]$谁大就行,如果$w[i]$大于$w[1]$就继续,否则就$break$。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int w[N];
int find(int x)
{
for(int i=1;i<=n;i++)
if(w[i]==x) return i;
return 0;
}
bool cmp(vector<int> &str1, vector<int> &str2, vector<int> &str)
{
vector<int> tmp;
for(auto u:str2) tmp.pd(u);
for(auto u:str1) tmp.pd(u);
for(int i=0;i<str.size();i++){
if(str[i]>tmp[i]) return false;
else if(str[i]<tmp[i]) return true;
}
return false;
}
inline void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i];
if(n==1) cout<<w[1]<<endl;
else{
int idx = find(n);
if(idx==1){
idx = find(n-1);
}
int j = idx-2;
while(j && w[j]>w[1]) j--;
vector<int> res;
for(int i=idx;i<=n;i++) res.pd(w[i]);
for(int i=idx-1;i>j;i--) res.pd(w[i]);
for(int i=1;i<=j;i++) res.pd(w[i]);
if(idx==n){
for(int i=n;i<2*n;i++){
if(res[i-n]>w[i>=(n+1)?i%(n+1)+1:i]) break;
else if(res[i-n]<w[i>=(n+1)?i%(n+1)+1:i]){
res.clear();
for(int i=n;i<2*n;i++) res.pd(w[i>=(n+1)?i%(n+1)+1:i]);
}
}
}
for(auto u:res) cout<<u<<" ";
cout<<endl;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
tql
🥰