The title
There is a classic partition process in the famous quicksort algorithm: we usually take an element as the pivot in some way, and by swapping, put the elements smaller than the pivot to its left and the elements larger than the pivot to its right. Given the permutation of N distinct positive integers after partition, how many elements may be the pivot elements selected before partition?
For example, given N=5, the permutations are 1, 3, 2, 4, 5. Is:
- There’s nothing to the left of 1, everything to the right is bigger, so it could be a pivot entry;
- Even though everything to the left of 3 is smaller, the 2 to the right of 3 is smaller, so it can’t be a pivot;
- Even though everything to the right of 2 is bigger, the 3 to the left is bigger, so it can’t be a pivot;
- For similar reasons, 4 and 5 could be pivot entries.
So there are three possible pivot entries.
Input format
The input gives a positive integer N (≤10^5) in line 1; The second line is a space-separated list of N distinct positive integers, each up to 10^9.
The output format
In line 1, print the number of elements that could be pivot elements; These elements are printed in ascending order on line 2, separated by one space, with no extra space at the beginning or end of the line.
Train of thought
As a boor, I must have thought of violence at first, going over every digit to see if any of them didn’t meet the criteria. Writing quickly and unfortunately running out of time.
//foreverking
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
int n,cnt;
vector<int> s;
vector<int> s1;
void check(int x,int j){
int flag = 1;
for(int i = 0; i < j; i ++){
if(s[i] > x){
flag = 0;
break; }}for(int i = n - 1; i > j; i--){
if(s[i] < x){
flag = 0;
break; }}if(flag){
s1.push_back(x);
cnt++;
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i++){
int a;
cin >> a;
s.push_back(a);
}
for(int i = 0; i < n; i++){
check(s[i],i);
}
cout << cnt << endl;
for(int i = 0; i < cnt; i++){
if(i ! =0)
cout << "";
cout << s1[i];
}
cout << endl;
return 0;
}
Copy the codeSo let’s go ahead and optimize, and since it’s going to time out, as long as the ith number is greater than the largest number to the left of I, and less than the smallest number to the right of I, it’s a pivot entry. If you want to be bigger than all the numbers on the left, that’s the same thing as being bigger than the maximum number on the left, and smaller than the minimum number on the right. So we can go from left to right, find the maximum number of digits that precede it; Iterate from right to left again, finding the smallest number following each digit. Notice that the maximum value of the first number to the left can be considered 0, and the minimum value of the last number to the right can be considered infinity, because they always have to satisfy this condition.
Details, ideas are in the notes:
//foreverking
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
int n, cnt;
int a,b;
int main(){
cin >> n;
vector<int> num; // Input data
vector<int> res; // Data that meets the condition
vector<int> maxx; // From left to right, the maximum value of each left bit
vector<int> minn; // From right to left, the smallest value to the right of each bit of data
for (int i = 0; i < n; i++){
int x;
cin >> x;
num.push_back(x); // Vector stores all data
}
a = num[0]; // Minimum initialization
b = num[n - 1]; // Initialize the maximum value
maxx.push_back(0); // Set the minimum value on the left of the first data to 0
minn.push_back(1000000001); // The maximum value on the right side of the last data is 10^9
for (int i = 0; i < n - 1; i++){ // Find the maximum left side of each digit, and notice that the NTH digit ends up being the left side of anything
if (num[i] > a)
a = num[i];// Save traversal to the current maximum number
maxx.push_back(a);// Press the largest number to the left of the ith number
}
for (int i = n - 1; i > 0; i--){ // Find the minimum value on the right-hand side of each digit, noting that the 1 ends, because 0 cannot be the right-hand side of any number
if (num[i] < b)
b = num[i];// Save traversal to the current minimum number
minn.push_back(b);// Press the smallest number to the right of the ith number
}
for (int i = 0; i < n; i++){
if (num[i] > maxx[i] && num[i] < minn[n - 1 - i]){ // The pivot element satisfies conditions that are greater than the maximum value on the left and smaller than the minimum value on the right
res.push_back(num[i]);
cnt++;
}
}
cout << cnt << endl;
//sort(res.begin(), res.end()); You don't have to sort, in fact, if you satisfy the pivot conditions, it must be increasing
// if (cnt){
// for (int i = 0; i < cnt - 1; i++)
// cout << res[i] << " ";
// cout << res[cnt - 1];
// }
// //0 pivot entries when considered separately, need to print a line of space, although I usually print this newline, accidentally not pit
//cout << endl;
for (int i = 0; i < cnt; i++){
if(i ! =0)
cout << "";
cout << res[i];
}
cout << endl;
return 0;
}
Copy the codeAlso check out the code in Areau. It’s always easy
Analysis: If the value to the left of the element is smaller than the value to the left of the element, it must be a pivot element. If the value to the left of the element is smaller than the value to the right of the element, it must be a pivot element. Then its rank must not change
//foreverking
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
int v[100001];
int main(){
int n, max = 0, cnt = 0;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++){
cin >> a[i];
b[i] = a[i];//b is a copy of A
}
sort(a.begin(), a.end());// sort a[]
for (int i = 0; i < n; i++){
if (a[i] == b[i] && b[i] > max)
v[cnt++] = b[i];
if (b[i] > max)
max = b[i];// Max is the largest number to the left of the number
}
cout << cnt << endl;
for (int i = 0; i < cnt; i++){
if(i ! =0)
cout << "";
cout << v[i];
}
cout << endl;
return 0;
}
Copy the codeTopic link