![打卡信奥刷题（3534）用C++实现信奥题 P10991 [蓝桥杯 2023 国 Python A] 选段排序](http://pic.xiahunao.cn/yaotu/打卡信奥刷题（3534）用C++实现信奥题 P10991 [蓝桥杯 2023 国 Python A] 选段排序)
P10991 [蓝桥杯 2023 国 Python A] 选段排序题目描述给定一个长度为nnn的序列AiA_iAi以及两个下标p,q(pq)p, q(p q)p,q(pq)。你可以选择任意一个区间[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输入 #15 1 4 4 5 3 3 1输出 #13说明/提示对于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实现#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN2e55;priority_queueint,vectorint,greaterintqn;priority_queueintqx;intn,p,q,a[N],ans;signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnpq;for(inti1;in;i)cina[i];for(intip;in;i){qn.push(a[i]);if(qx.size()q-p1)qx.push(a[i]);elseif(a[i]qx.top()){qx.pop();qx.push(a[i]);}ansmax(ans,qx.top()-qn.top());}while(qx.size())qx.pop();while(qn.size())qn.pop();for(intiq;i1;--i){qx.push(a[i]);if(qn.size()q-p1)qn.push(a[i]);elseif(a[i]qn.top()){qn.pop();qn.push(a[i]);}ansmax(ans,qx.top()-qn.top());}coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
P10991 [蓝桥杯 2023 国 Python A] 选段排序题目描述给定一个长度为nnn的序列AiA_iAi以及两个下标p,q(pq)p, q(p q)p,q(pq)。你可以选择任意一个区间[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输入 #15 1 4 4 5 3 3 1输出 #13说明/提示对于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实现#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN2e55;priority_queueint,vectorint,greaterintqn;priority_queueintqx;intn,p,q,a[N],ans;signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnpq;for(inti1;in;i)cina[i];for(intip;in;i){qn.push(a[i]);if(qx.size()q-p1)qx.push(a[i]);elseif(a[i]qx.top()){qx.pop();qx.push(a[i]);}ansmax(ans,qx.top()-qn.top());}while(qx.size())qx.pop();while(qn.size())qn.pop();for(intiq;i1;--i){qx.push(a[i]);if(qn.size()q-p1)qn.push(a[i]);elseif(a[i]qn.top()){qn.pop();qn.push(a[i]);}ansmax(ans,qx.top()-qn.top());}coutans;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
