本文最后更新于：1 年前
题目大意：
判断最大排序范围。
解题思路：
思维僵化复建ing，太久不写题想复杂了，最后借鉴了才恍然大悟。其实只要判断修改过的就可以了，在在此基础上向两侧延伸直到b数组不符合非降序即可
代码：
我原写的：
（样例也过了一些，但是改来改去始终卡）；；；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<bits/stdc++.h>
using namespace std;
void solve(){
int n,x;
cin>>n;
map<int,int>mp;
vector<int>a,b;
for(int i=0;i<n;i++){
cin>>x;
a.push_back(x);
}
a.push_back(0);
for(int i=0;i<n;i++){
cin>>x;
b.push_back(x);
}
b.push_back(0);
int l=0,r=0,maxv=0,ml=0,mr=0;
string as="",bs="";
for(int i=0;i<n;i++){
mp[a[i]]++;
mp[b[i]]++;
as+='0'+a[i];
bs+='0'+b[i];
r=i;
int flag=0;
for(auto it:mp){
if(it.second%2!=0&&a[l]!=it.first){
flag=1;
break;
}else if(it.second%2!=0&&a[i]==it.first){
l++;
}
}
if(!flag&&maxv<=(r-l)&&as!=bs){
maxv=r-l;
ml=l;
mr=r;
}
if(b[i]>b[i+1]&&i!=n-1){
as="";
bs="";
l=r+1;
mp.clear();
}
}
cout<<ml+1<<' '<<mr+1;
}
int main(void){
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
solve();
cout<<endl;
}
}
|
借鉴后：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
void solve(){
int n,x;
cin>>n;
vector<int>a(1,0),b(1,0);
for(int i=1;i<=n;i++){
cin>>x;
a.push_back(x);
}
int l=-1,r=-1;
for(int i=1;i<=n;i++){
cin>>x;
b.push_back(x);
if(b[i]!=a[i]&&l==-1){
l=i;
}else if(b[i]!=a[i]&&l!=-1){
r=i;
}
}
while(l>=0){
if(b[l-1]>b[l])break;
l--;
}
while(r<n){
if(b[r+1]<b[r])break;
r++;
}
if(l<=0)l=1;
if(r>n)r=n;
cout<<l<<' '<<r<<endl;
}
int main(void){
int t;
cin>>t;
while(t--){
solve();
}
}
|