P9742题解

_VEGETABLE_OIer_xlc · 2023-07-25 19:01:47 · 题解

题目传送门

这道题很简单，但坑点很多，包括我也因为踩了其中一个坑导致比赛时挂到 40 分。

下面让本蒟蒻带领大家排疑解难！

题意

给定 n 个等差数列 a_i 的首项 a_{i,0}，等差数列的项数为 m+1，要求把这些等差数列按字典序排序，特别的，第 i 个等差数列的第 j 项 a_{i,j}=a_{i,j-1} \times i。

初看这道题：由于要输出每个等差数列 a_i 的下标 i，所以想到用结构体的方式记录首项 a_{i,1} 和 i 是理所当然的。

接着就是排序，输出编号啦。

我们需要找到 两个等差数列中第一次出现的不同的数，比较大小。所以要用个函数来帮助排序。

首先肯定是比较首项。

首项相同怎么办呢？那就比较第二项！由于首项一样，每个等差数列的下标肯定不一样，所以第一项相同，第二项肯定不同！

下面说一说这道题用这种思路的坑点：

• 虽然题目告诉我们有负数，但不用慌，这种做法是纯用字典序排，大就是往后排，小就是往前排。

• 要开 long long。这种做法没开会挂了 60 分

好了上代码！

#include<bits/stdc++.h>
using namespace std;
long long n,m;
struct node
{
    long long a,num;
}q[114514];
bool cmp(node c,node d)
{
    if(c.a>d.a)return false;
    else if(c.a==d.a)
    {
        long long f=c.a,g=d.a;
        f*=c.num;g*=d.num;
        if(f>g)return false;
        else return true;
    }
    else return true;
}
int main(){
    cin>>n>>m;
    for(long long i=1;i<=n;i++)
    {
        cin>>q[i].a;
        q[i].num=i;
    }
    sort(q+1,q+n+1,cmp);
    for(long long i=1;i<=n;i++)
        cout<<q[i].num<<" ";
    return 0; 
}

忠告

十年 OI 一场空，不开 long long 见祖宗。