30分TLE,望优化

P1678 烦恼的高考志愿

A宋锦瑞A @ 2021-07-15 21:51:19

代码如下

#include<bits/stdc++.h>

using namespace std;

int n,m,mins,ans,res;
int a[100001];
int b[100001];

int main()
{
    cin>>m>>n;
    for(int i=0;i<=m-1;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<=n-1;i++)
    {
        cin>>b[i];
    }
    for(int i=0;i<=n-1;i++)
    {
        mins=10000001;
        for(int j=0;j<=m-1;j++)
        {
            res=a[j]-b[i];
            if(res<0)
            {
                res-=res*2;
            }
            if(mins>res)
            {
                mins=res;
            }
        }
        ans+=mins;
    }
    cout<<ans;

    return 0;
}

by qqqqq111 @ 2021-07-15 21:54:31

这不是正解,怎么优化都过不了,换种思路吧


by ningmengcha @ 2021-07-26 14:23:28

二分试试


by nju181840342 @ 2021-08-03 18:44:16

这个时间复杂度是n*m,n,m等于十万就炸了。如果先排序再二分是

(n+m)\log m

就不会TLE


|