警示后人+求助

P1923 【深基9.例4】求第 k 小的数

mc_xiexie @ 2023-11-11 17:12:54

这个题数据巨大,巨多,直接这样会TLE两个点

#include<bits/stdc++.h>//万能头文件
using namespace std;
int main(){
    int n,m,a[5000000];//定义数组、变量
    cin>>n>>m;//输入n、k
    for(int i=0;i<n;i++){
        cin>>a[i];//输入数据,在这会TLE
    }
    sort(a,a+n);//排序
    cout<<a[m];//输出
     return 0;//返回0
}

求助(别骂,谢谢)

TLE后的我看了看题解,不错。

都是nth_element或分治。

我就想能不能用字符串提取数字来做

然后——输出只有0;

就想求助一下(别骂,谢谢)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int b[5000000];
    int n,k,sum,g,t;
    double ant=0;
    cin>>n>>k;
    char a[99999999];
    gets(a);
    for(int i=0;i<n+n+1;i++){
        if(a[i]==' '){
            for(int q=sum+1;q<i;q++){
                g=pow(10,i-sum);
                t=a[q];
                ant+=t%g;
                sum++;
            }
            sum++;
        }
    }
    sort(b,b+n);
    cout<<b[k];
}

by mc_xiexie @ 2023-11-11 17:13:40

骂轻点,谢谢


by pies_0x @ 2023-11-11 17:28:42

呃.......

应该是加强数据了


by pies_0x @ 2023-11-11 17:29:00

@mc_xiexie


by diamond_153 @ 2023-11-11 17:58:13

@mc_xiexie 在输入前加上 ios::sync_with_stdio(false); 试试?


by Hatsunatsu @ 2023-11-11 17:59:48

@mc_xiexie 输入量大的话用 cin 会很慢的。建议关同步或者使用 c 风格的 scanf 输入。


by diamond_153 @ 2023-11-11 18:01:01

@mc_xiexie 关闭同步流后开 O2 优化能过,但是标准解法是分治求解,直接输入输出是不会 TLE 的。


|