企业官网建设流程全解析

P10991 [蓝桥杯 2023 国 Python A] 选段排序

题目描述

给定一个长度为nnn的序列AiA_iAi​以及两个下标p,q(p<q)p, q(p < q)p,q(p<q)。你可以选择任意一个区间[L,R][L, R][L,R]并将序列的这个范围内的元素AL∼ARA_L \sim A_RAL​∼AR​从小到大排序。

求选择一个区间排序后Aq−ApA_q − A_pAq​−Ap​的值最大可以是多少。

输入格式

输入的第一行包含三个整数n,p,qn, p, qn,p,q，相邻两个整数之间使用一个空格分隔。

第二行包含nnn个整数，分别表示A1,A2,⋯ ,AnA_1, A_2, \cdots, A_nA1​,A2​,⋯,An​，相邻两个整数之间使用一个空格分隔。

输出格式

输出一行，包含一个整数表示Aq−ApA_q − A_pAq​−Ap​的最大值。

输入输出样例 #1

输入 #1

5 1 4 4 5 3 3 1

输出 #1

3

说明/提示

对于20%20\%20%的评测用例，n≤100,Ai≤200n \le 100 ,A_i \le 200n≤100,Ai​≤200；

对于40%40\%40%的评测用例，n≤2000,Ai≤3000n \le 2000 ,A_i \le 3000n≤2000,Ai​≤3000；

对于所有评测用例，1≤p≤q≤n≤2×105,1≤Ai≤1061 \le p \le q \le n \le 2 \times 10^5,1 \le A_i \le 10^61≤p≤q≤n≤2×105,1≤Ai​≤106。

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=2e5+5;priority_queue<int,vector<int>,greater<int>>qn;priority_queue<int>qx;intn,p,q,a[N],ans;signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>p>>q;for(inti=1;i<=n;++i)cin>>a[i];for(inti=p;i<=n;++i){qn.push(a[i]);if(qx.size()<q-p+1)qx.push(a[i]);elseif(a[i]<qx.top()){qx.pop();qx.push(a[i]);}ans=max(ans,qx.top()-qn.top());}while(qx.size())qx.pop();while(qn.size())qn.pop();for(inti=q;i>=1;--i){qx.push(a[i]);if(qn.size()<q-p+1)qn.push(a[i]);elseif(a[i]>qn.top()){qn.pop();qn.push(a[i]);}ans=max(ans,qx.top()-qn.top());}cout<<ans;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容