1 条题解

  • 0

    真是最舒服的一次了。

    题也不难,状态也好。

    赛时代码,就是求 ans=ans=nn 为结尾的最长下降子序列长度,要求数值连续而已。

    最后输出 n-ans 。

    赛时代码

    //t3 
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    
    const int N=2e5+10;
    int n,a[N],maxx,flag,ans;
    
    signed main()
    {
    	scanf("%lld",&n);
    	for(int i=1;i<=n;++i)
    	{
    		scanf("%lld",&a[i]);
    		if(a[flag]<a[i])flag=i;
    	}
    	maxx=a[flag];
    	while(flag)
    	{
    		bool fd=0;
    		for(int i=flag;i>=1;--i)
    		{
    			if(a[i]==maxx)
    			{
    				fd=1;
    				flag=i-1;
    				maxx--;
    				ans++;
    				break;
    			}
    		}
    		if(!fd)
    		{
    			break; 
    		}
    	}
    	printf("%lld",n-ans);
    	return 0;
    } 
    
    • @ 2024-8-8 18:12:47
      #include<bits/stdc++.h>
      using namespace std;
      const int N=2e5+5;
      int n,a[N],b[N]; 
      signed main()
      {
          scanf("%d",&n);
          for(int i=1;i<=n;i++) scanf("%d",&a[i]);
          for(int i=1;i<=n;i++) b[a[i]]=i;
          b[0]=n+1;
          for(int i=n;i>=1;i--) 
      		if(b[i]<b[i-1])
      		{
      			printf("%d\n",i-1);
      			return 0; 
      		}
          return 0;
      }
      
  • 1

信息

ID
2998
时间
1000ms
内存
256MiB
难度
7
标签
递交数
142
已通过
30
上传者