Codeforces Round #591 (Div. 2)D. Sequence Sorting(思路)
程序员文章站
2022-06-18 11:26:55
...
题目链接:
https://codeforces.com/problemset/problem/1223/D
题面:
题意:
一次操作可以把一种数字(不一定是只有一个)移动到最左边或最右边,问最少经过几次操作可以使序列变成不下降序列。ps:没初始化了,数组开小了,我sb了
思路:
考虑不需要移动的(也就是本身连续不减)数,这里用邻接表的形式存某种数的出现坐标,对数据去重,然后用表示当前需要移动的数数量,通过当前数出现的最后一个位置和下一个数出现的第一个位置从而判断当前数是否是不需要移动的,然后累加取最大值,最后用总的数的种类减去不需要移动的种类就是答案。
参考代码:
/* CF was purple years ago!
* Thanks cf-tool!
* Author: nuoyanli
* Time: 2019-12-08 12:59:09
**/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 10;
ll n,t,sum,a[N],b[N];
vector<int>mmp[N];
ll solve() {
sort(a+1,a+n+1);
int num=unique(a+1,a+n+1)-a-1;
/* for(int i=1;i<=num;i++){
cout<<a[i]<<" ";
}
cout<<endl;
*/
ll ans=1;
sum=1;
for(int i=1; i<num; i++) {
int x=a[i],y=a[i+1];
if(mmp[x].back()>mmp[y][0]) {
sum=1;
} else {
sum+=1;
}
ans=max(ans,sum);
}
return num-ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>t;
while(t--) {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
b[i]=a[i];
mmp[a[i]].push_back(i);
}
cout<<solve()<<endl;
for(int i=1; i<=n; i++) {
mmp[b[i]].clear() ;
}
}
return 0;
}
上一篇: java——线程同步的有关知识
下一篇: Java中有关HttpClient知识
推荐阅读
-
Codeforces Round #271 (Div. 2) D. Flowers (递推 预处理)_html/css_WEB-ITnose
-
Codeforces Round #688 (Div. 2) D. Checkpoints gym 102881 L. The Expected Square A. Sticker Album
-
Codeforces Round #482 (Div. 2) D. Kuro and GCD and XOR and SUM(数学+01字典树)(好题)
-
Codeforces Round #FF (Div. 2) D. DZY Loves Modification 贪心+优先队列_html/css_WEB-ITnose
-
Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
-
Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree(dfs)
-
Codeforces Round #619 (Div. 2) D. Time to Run
-
Codeforces Round #583 (Div. 1 + Div. 2,) D. Treasure Island(dfs+思维)
-
Codeforces Round #533 (Div. 2) D. Kilani and the Game(bfs+模拟)
-
Codeforces Round #643 (Div. 2) D. Game With Array