蜜汁TLE
查看原帖
蜜汁TLE
241817
Chancylaser楼主2021/8/21 16:23

对拍题解没错,随机大样例速度贼快,o(n)时间复杂度,但是提交上去还是Tle,不知道咋办了,有神仙帮蒟蒻看看嘛。

#include<cstdio>
#include<cstring>
using namespace std;
int n,t;
char s[200005];
int a[200005];
int top;
int num;
int endd;
char eee;
int main(){
    //freopen("qwq.txt","r",stdin);
    //freopen("qaq.txt","w",stdout);
    scanf("%d%d",&n,&t); 
    eee=getchar();
    gets(s);
    for(int i=0;i<strlen(s);i++){
        if(s[i]=='.'){
            a[i+1]=-1;
            top=i+1;
            continue;
        }
        a[i+1]=s[i]-'0';
    }
    n=strlen(s);
    for(int i=top+1;i<=n;i++){
        if(a[i]>=5&&t>=1){
            t--;
            a[i]=-2;
            if(i-1==top){
                endd=i-2;
                a[i-2]++;
                num=666666;
                break;
            }
            endd=i-1;
            a[i-1]++;
            num=i-1;
            break;
        }
        if(t==0)
            break;
    }
    if(num!=666666){
        for(int i=num;i>top;i--){
            if(a[i]>=5&&t>=1){
                t--;
                a[i]=-2;
                if(i-1==top){
                    endd=i-2;
                    a[i-2]++;
                    break;
                }
                endd=i-1;
                a[i-1]++;       
            }       
            if(t==0)
                break;
        }
    }
    for(int i=endd;i>=1;i--){
        if(i-1==top){
            if(a[i]>=10){
                a[i-2]++;
                a[i]-=10;
            }
            else
                break; 
            i--;
            continue;
        }
        if(a[i]>=10){
            a[i-1]++;
            a[i]-=10;
        }
        else
            break;
    }
    if(a[0]!=0)
        printf("%d",a[0]);
    for(int i=1;i<=n;i++){
        if(i==top){
            if(a[i+1]==-2)
                break;
            printf(".");
            continue;
        }
        if(a[i]==-2){
            break;
        }
        printf("%d",a[i]);
    }
    return 0;
}
2021/8/21 16:23
加载中...