有时候卡常就是很玄学

Special_Judge · 2023-09-23 18:14:58 · 个人记录

试对比以下两段代码：

代码一：

pair<long long,int> a[N];
bool cmp(pair<long long,int> x,pair<long long,int> y)
{
    return x.first==y.first?x.second<y.second:x.first>y.first;
}
...
int main()
{
    ...
    while(m--)
    {
        ...
        for(int i=1;i<=n;i++)
        {
            a[i].first=1ll*t*v[i]+s[i];
            a[i].second=i;
        }
        nth_element(a+1,a+k,a+1+n,cmp);
        print(a[k].second);//注：为快速输出
        putchar('\n');
    }
    ...
}

代码二：

int a[N];
bool cmp(int x,int y)
{
    return 1ll*t*v[x]+s[x]==1ll*t*v[y]+s[y]?x<y:1ll*t*v[x]+s[x]>1ll*t*v[y]+s[y];
}
...
int main()
{
    ...
    for(int i=1;i<=n;i++)
        a[i]=i;
    while(m--)
    {
        ...
        nth_element(a+1,a+k,a+1+n,cmp);
        print(a[k]);//注：为快速输出
        putchar('\n');
    }
    ...
}

这两段代码的时间复杂度显然都为 O(nm)，猜猜哪段跑得快？

答案是第二段，在 n=m=7000 的数据下能跑出 170ms，第一段则跑到了 520ms。

原题时限 350ms。

我卡了一个半小时。