新人求助,10个全WA,自己造的小数据到是过了

Star· @ 2017-02-12 23:43:16

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
long long int sch[100001],stu[100001];
long long int m,n,i,j,ans,mid;
int erfen(int num,int first,int last)
{
    mid=(first+last)/2;
    if(sch[mid]>stu[num] && sch[mid-1]>stu[num])
        erfen(num,first,mid);
    else if(sch[mid]<stu[num] && sch[mid+1]<stu[num])
        erfen(num,mid,last);
    if(sch[mid]>stu[num] && sch[mid-1]<stu[num])
        return min( sch[mid]-stu[num] , stu[num]-sch[mid-1] );
    else if(sch[mid]<stu[num] && sch[mid+1]>stu[num])
        return min( stu[num]-sch[mid] , sch[mid+1]-stu[num] );
}
int main()
{
    cin>>m>>n; // m学校数,n学生数
    for ( i=1; i<=m; i++)
        cin>>sch[i];
    for ( i=1; i<=n; i++)
        cin>>stu[i];
    sort(sch+1,sch+1+m);
    sort(stu+1,stu+1+n);
    for( i=1; i<=n; i++)
    {
        if(stu[i]<=sch[1] )
            ans+= ( sch[1]-stu[i] );
        else if(stu[i]>=sch[m] )
            ans+= ( stu[i]-sch[m] );
        else
            ans+= erfen(i,1,m);
    }
    cout<<ans;
    return 0;
}

by Star· @ 2017-02-12 23:44:29

希望大佬们能帮我解答下 我的哪里错了

by Star· @ 2017-02-12 23:59:16

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
long long int sch[100001],stu[100001];
long long int m,n,i,j,ans,mid;
int erfen(int num,int first,int last)
{
    int mid=(first+last)/2;
    if(sch[mid]>stu[num] && sch[mid-1]>stu[num])
        return erfen(num,first,mid);
    else if(sch[mid]<stu[num] && sch[mid+1]<stu[num])
        return erfen(num,mid,last);
    if(sch[mid]>stu[num] && sch[mid-1]<stu[num])
        return min( sch[mid]-stu[num] , stu[num]-sch[mid-1] );
    else if(sch[mid]<stu[num] && sch[mid+1]>stu[num])
        return min( stu[num]-sch[mid] , sch[mid+1]-stu[num] );
}
int main()
{
    cin>>m>>n; // m学校数,n学生数
    for ( i=1; i<=m; i++)
        cin>>sch[i];
    for ( i=1; i<=n; i++)
        cin>>stu[i];
    sort(sch+1,sch+1+m);
    sort(stu+1,stu+1+n);
    for( i=1; i<=n; i++)
    {
        if(stu[i]<=sch[1] )
            ans+= ( sch[1]-stu[i] );
        else if(stu[i]>=sch[m] )
            ans+= ( stu[i]-sch[m] );
        else
            ans+= erfen(i,1,m);
    }
    cout<<ans;
    return 0;
}
修改了下还是10个WA.....大家帮我修改下这个代码把,一楼的不要看了

by DDullahan @ 2017-04-01 20:44:43

你这个貌似问题就是在 sch排序后的中断如果出现重复的就gg了

推荐一：

unique去重（自行百度）

推荐二：

二分直接用sch的key值比较去找就行了

没有必要在搜索的时候去考虑sch[mid+1]之类的

直接在搜索结束时判断一下 sch[ans+1],sch[ans],sch[ans-1] 对结果的改变就行了

推荐三：

入STL邪教吧

（仅供参考 欢迎交流）

@ Star·

by DDullahan @ 2017-04-01 20:45:15

@Star·

by Star· @ 2017-04-02 18:08:54

@@ salt_fish_swjtu 谢谢

by Star· @ 2017-04-02 18:09:44

@ salt_fish_swjtu

by Star· @ 2017-04-08 10:50:25

@salt_fish_swjtu 我错在了少判断了“=”上， 不过谢谢你啦

by DDullahan @ 2017-04-21 20:26:45

@ Star· 对的 所以可以考虑去重(时间太长 具体题目是啥我也忘了ღ( ´･ᴗ･` ))

by 奋斗の阿峰 @ 2020-08-24 12:38:34

@DDullahan 去重真的管用诶，谢谢