【枚举】CF1833 D

深碍√TFBOYSˉ_ 2024-03-22 19:49 77阅读 0赞

[Problem - D - Codeforces][]

题意：

给定一个序列，让你找一个区间，翻转区间内的数，交换前缀和后缀，让结果数组的字典序最大

![c14db1d7bfb54ba49242f5a34dbd103d.png][]

![ee072aabc4d74be989ee71d7bcdc70ec.png][] ![ee70de4d7de04a2895c332ea9f048bb4.png][]

思路：

观察样例可知，r是可以直接确定的，l是不确定的，因此考虑O(N)枚举左端点，统计字典序最大值

关于字典序，放vector里可以直接比较

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std; 
    
    const int mxn=2e5+10;
    
    int N;
    
    vector<int> a(N,0);
    
    vector<int> calc(int l,int r){
    	vector<int> res;
    	for(int i=r+1;i<N;i++) res.push_back(a[i]); 
    	for(int i=r;i>=l;i--) res.push_back(a[i]);
    	for(int i=0;i<l;i++) res.push_back(a[i]); 
    	return res;
    }
    void solve(){
    	cin>>N;
    	a.resize(N,0);
    	vector<int> res(N,0);
    	int l=0,r=0;
    	for(int i=0;i<N;i++){
    		cin>>a[i];
    		if(a[i]==N){
    			r=i;
    		}
    	}
    	if(r==0){
    		for(int i=0;i<N;i++){
    			res[i]=0;
    			if(a[i]==N-1){
    				r=i;
    			}
    		}
    	}
    	if(r!=N-1) r--;
    	for(int l=0;l<=r;l++){
    		auto t=calc(l,r);
    		if(t>res){
    			res=t;
    		}
    	}
    	for(int i=0;i<res.size();i++) cout<<res[i]<<" \n"[i==res.size()-1];
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1833/problem/D
[c14db1d7bfb54ba49242f5a34dbd103d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/937326682aa14b4f9a5e9e1a09765f51.png
[ee072aabc4d74be989ee71d7bcdc70ec.png]: https://img-blog.csdnimg.cn/ee072aabc4d74be989ee71d7bcdc70ec.png
[ee70de4d7de04a2895c332ea9f048bb4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d465bdfa448045af9f63cb7f3efaa236.png