暗网是什么网站,工作证明模板下载,网页设计与网站开发试题答案,wordpress 表格主题C. Min Max Sort
很不错的一道题目#xff0c;不过脑电波和出题人每对上#xff0c; q w q 。 qwq。 qwq。 正难则反。 我们考虑最后一步是怎么操作的。 最后一步一定是对 1 1 1和 n n n进行操作 那么上一步呢#xff1f; 上一步应该是对 2 2 2和 n − 1 n-1 n−1 以此类推…C. Min Max Sort
很不错的一道题目不过脑电波和出题人每对上 q w q 。 qwq。 qwq。 正难则反。 我们考虑最后一步是怎么操作的。 最后一步一定是对 1 1 1和 n n n进行操作 那么上一步呢 上一步应该是对 2 2 2和 n − 1 n-1 n−1 以此类推 第一步应该是对 n 2 \frac{n}{2} 2n和 n 2 1 \frac{n}{2}1 2n1 我们的答案应该是上一步之前的所有操作次数加上最后一步的操作次数。 然后对于 i ∈ [ 1 , n 2 ] i \in [1, \frac{n}{2}] i∈[1,2n]并不是所有 i i i都需要进行操作的。 如果本身 i i i到 n − i 1 n-i1 n−i1已经是有序的就不需要进行操作了。 如何判断是不是有序的呢 这里预处理出来一个 f i f_i fi表示以 i i i结尾的最长连续上升序列的长度。 如果 f [ n − i 1 ] n − i 1 − i 1 f[n-i1]n-i1-i1 f[n−i1]n−i1−i1说明这个 i i i到 n − i 1 n-i1 n−i1不是有序的则需要进行一次操作 #include bits/stdc.h#define int long long
#define rep(i, a, b) for(int i (a); i (b); i)
#define fep(i, a, b) for(int i (a); i (b); --i)
#define _for(i, a, b) for(int i(a); i(b); i)
#define pii pairint, int
#define pdd pairdouble,double
#define ll long long
#define db double
#define endl \n
#define x first
#define y second
#define pb push_back
#define vi vectorintusing namespace std;
const int maxn 2e5 10;
int n,a[maxn],f[maxn];void solve() {cinn;int lst0;rep(i,1,n){f[i]0;cina[i];}rep(i,1,n) {f[a[i]]f[a[i]-1]1;}int ans0;fep(i,n/2,1){if(f[n-i1]n-i1-i1){ans;}}coutansendl;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen(C:\\Users\\24283\\CLionProjects\\untitled2\\1.in, r, stdin);int _;cin _;while (_--)solve();return 0;
}
