C题双指针做法 75% TLE 求助

#include<bits/stdc++.h>
using namespace std;
#define PI 3.141****53589
#define int long long
const int N=2e5+10,mod=1e9+7;
int a[N];

signed main(){
    int n;cin>>n;
    
    for(int i=1;i<=n;i++){
//         cin>>a[i];
        scanf("%d",&a[i]);
    }
    int x;cin>>x;
//     cout<<x<<endl;
    int cnt=1;
    
    if(n==1){
        cout<<1;
        return 0;
    }
    
    else
    {
        for(int i=2,j=n+1;i<=j;i++){
            int t=j;
            cnt++;
            while(a[t]<=x&&t>i) t--;//找到当前x左边第一个比他大的数字

            if(a[t]>x){
                a[t]=x;
                j=t;

            }

        
        }
        cout<<cnt<<endl;   
    }
    return 0;
}

全部评论
第29行你这样找是n^2,要把下一个位置提前预处理出来
点赞 回复 分享
发布于 2022-04-08 21:13
如果左边找不到可爱值比唧唧大的,那就只有一种方案,就是一个一个出队,每出队一个就花费一分钟,所以把答案直接加上唧唧前面还有几只猫就是答案了
点赞 回复 分享
发布于 2022-04-08 21:15

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务