当前位置:网站首页>Cdeforces 1638 C. inversion graph - simple thinking

Cdeforces 1638 C. inversion graph - simple thinking

2022-06-12 13:33:00 Tianyi City*

This way

The question :

Give you a length of n Permutation ,i and j They can be connected if and only if i>j && p[i]<p[j]. How many connecting blocks are there .

Answer key :

At first glance, it is called join search , But it doesn't need to , It's more stupid to write and search the collection .
Fully understand any topic , Make good use of the conditions , Since this problem is arranged , That is to say if i Not in front i A place , Then it must be able to connect with the front .
So where is it connected ?
set up mx Before mx Location p The maximum of , If mx Not before , Then there will be no new connected block . Otherwise, a connected block will be added , Like 2 3 1 5 4.
In the first position ,mx=2, Then it means that this connected block can at least be connected to 2 Location , here we are 2 When mx by 3, That is to say, this connected block can at least be connected to 3.
here we are 4 When ,mx=3, In other words, you need to add a new connection block . Next mx=5 Can be connected to at least 5.

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
int main()
{
    
    int t;
    scanf("%d",&t);
    while(t--){
    
        int n;
        scanf("%d",&n);
        int mx=0,ans=0;
        for(int i=1;i<=n;i++){
    
            scanf("%d",&a[i]);
            if(mx>=i){
    
                mx=max(mx,a[i]);
                continue;
            }
            mx=a[i];
            ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

原网站

版权声明
本文为[Tianyi City*]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/03/202203010516109214.html