D. Sequence Sorting

제목:

입력은 q(3e5)q(3e5)q(3e5)조 데이터 각 조 데이터 입력 n(∑n≤3e5)n(\sum n\leq3e5)n(∑n≤3e5) 다음 행은 a 1, a 2,..., a n(1≤a i≤n)a1,a_2,\dots,a_n(1\leq a i\leq n)a1, a2,..., an(1≤ai≤n) 한 번의 조작으로 한 숫자를 가장 왼쪽 또는 가장 오른쪽으로 이동할 수 있으며, 최소 몇 번의 조작을 거치면 서열이 내려가지 않는 서열로 변할 수 있는지 묻는다.

문제 풀이:

모든 숫자를 한 번만 이동시켜 숫자를 이산화시키고 서열의 질서성을 관찰하는 것도 괜찮다.사실 하나의 성질을 발견할 수 있다. 연속적으로 질서가 있는 부분의 숫자는 움직이지 않고 다른 숫자는 왼쪽으로 이동하거나 오른쪽으로 이동하기 때문에 연속적으로 질서가 있는 부분의 길이를 최대화하면 된다.

코드:

#include
using namespace std;
const int N=3e5+9;
int q,a[N],n,b[N];
bool vis[N];
int f[N];
vector<int>g[N];
int dp[N];
void solve(){
    //memset(dp,0,sizeof(dp));
    sort(b+1,b+n+1);int nb;
    nb=unique(b+1,b+n+1)-b-1;
   // for(int i=1;i<=nb;i++)cout<
    int ans=1;dp[1]=1;
    for(int i=1;i<nb;i++){
        int x=b[i],y=b[i+1];
        if(g[x].back()<g[y][0])dp[i+1]=dp[i]+1;else dp[i+1]=1;
        ans=max(ans,dp[i+1]);
    }
    cout<<nb-ans<<endl;
}
int main(){
 //   freopen("tt.in","r",stdin),freopen("tt.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>q;
    while(q--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i],g[a[i]].push_back(i);
        solve();
        for(int i=1;i<=n;i++)g[a[i]].clear();
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

codeforce 991E(조합수 반복 검색)

제목 링크: 링크 열기 클릭 샤오밍이 헷갈릴 때 본 자동차 번호판 숫자를 실제 숫자와 비교해 보자. ① 실제로 나온 숫자는 샤오밍이 다 봤다 ② 샤오밍은 같은 숫자만 보고 적을 수는 없다 ③ 차량 번호는 전도 제로가...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다