0分超时求助

P1678 烦恼的高考志愿

GXA3336gxa @ 2024-01-24 11:25:40

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long m,a[1000005],n,b[1000005],ans=0,s[1000005],d,e;
    cin>>m>>n;
    for(int i=1;i<=m;i++)cin>>a[i];//输入分数线 
    sort(a+1,a+m+1);//从小到大排分数线 
    for(int j=1;j<=n;j++)cin>>b[j];//输入估分 
    for(int x=1;x<=m;x++){
        for(int y=1;y<=n;y++){
            if(a[y]<=b[x]){//二分 
                s[y]=b[x]-a[y];
                sort(s+1,s+y+1);//排序 
                d=s[1];//取最小 
                memset(s,0,sizeof(s));//s归零 
            }
            else
            if(a[y]>=b[x]){
                s[y]=a[y]-b[x];
                sort(s+1,s+y+1);//排序
                e=s[1];//取最小 
                memset(s,0,sizeof(s));
            }
            if(d>e)ans+=e;
            else
            if(d<e)ans+=d;
        }
    }
    cout<<ans<<endl;
    return 0;
}

以上为0分代码


by Whycmd @ 2024-01-24 11:44:23

@gxa3336 这段代码的时间复杂度不能达到题目要求,为 O(n^3log n) (两层循环+sort固定nlogn),所以会超时(本题要求时间复杂度在 O(nlogn)(30分要求O(n^2logn))内),因此你的思路似乎有一些问题,建议是最好重写.


|