0分求助（玄关）

P5740 【深基7.例9】最厉害的学生

ikun_HYZ @ 2024-02-01 20:11:21

#include<bits/stdc++.h>
using namespace std;
struct node{
    string n;
    int c,m,e,sum=0;
}a[1010];
bool cmp(node x,node y){
    return x.sum>y.sum;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].n>>a[i].c>>a[i].m>>a[i].e;
        a[i].sum+=a[i].c+a[i].m+a[i].e;
    }
    sort(a,a+n,cmp);
    printf("%s %d %d %d",a[0].n,a[0].c,a[0].m,a[0].e);
    return 0;
}

by yucheng0630 @ 2024-02-01 20:13:12

@ikun_HYZ

结构体排序

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
struct stu{
    string name;
    int yw;
    int sx;
    int yy;
    int zf;
    int id;
}; 
bool cmp(stu x,stu y){
    if(x.zf==y.zf){
        if(x.id>y.id){
            return 0;
        }
        else{
            return 1;
        }
    }
    if(x.zf>y.zf){
        return 1;
    }else{
        return 0;
    }
}
int main(){
    int n;
    stu a[maxn];
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].name>>a[i].yw>>a[i].sx>>a[i].yy;
        a[i].zf=a[i].yw+a[i].sx+a[i].yy;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=1;i++){
        cout<<a[i].name<<" "<<a[i].yw<<" "<<a[i].sx<<" "<<a[i].yy;
    }
    return 0;
}

by Trump_ @ 2024-02-01 20:13:46

要输出靠前的一位，建议用stable_sort

by Trump_ @ 2024-02-01 20:14:46

@Trump_ 坏了，stable_sort好像不对QAQ

by Trump_ @ 2024-02-01 20:18:26

额，你输出也错了，直接cout就行

by Trump_ @ 2024-02-01 20:21:20

#include<bits/stdc++.h>
using namespace std;
struct node{
    string n;
    int c,m,e,sum=0;
}a[1010];
bool cmp(node x,node y){
    return x.sum>y.sum;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].n>>a[i].c>>a[i].m>>a[i].e;
        a[i].sum+=a[i].c+a[i].m+a[i].e;
    }
    stable_sort(a,a+n,cmp);
    cout<<a[0].n<<' '<<a[0].c<<' '<<a[0].m<<' '<<a[0].e<<'\n';
    return 0;
}

stable_sort是归并排序，当键值一样时不会改变顺序。

sort是快速排序，有可能在键值一样时改变顺序

by xiaoshumiao @ 2024-02-01 20:24:24

楼上正解，string 不能用 cout 输出。

by ikun_HYZ @ 2024-02-01 20:28:06

谢谢大佬们！已关注！

此贴结

by masonxiong @ 2024-02-01 20:32:11

先说问题吧，stl 自带的 sort 是快排 / 堆排，速度很快，但并不稳定（所谓稳定，是排序前任意两个关键字相同的元素的顺序在排序后保证保持不变）举个例子：

我们有以下几名学生以及它们的总成绩：

xiaoming 114514
xiaoliang -999999
xiaohong 114514

我们以这些同学的总成绩作为关键字进行排序，使用 std::sort() 可能会是这样：

xiaohong 114514
xiaoming 114514
xiaoliang -999999

这里 xiaohong 和 xiaoming 虽然总成绩相同，但是 xiaoming 的输入顺序在前，按理来说应当排在 xiaohong 前面，但是因为其不稳定性，导致他们的顺序发生变化，这就是你错的原因。

那么如何规避这个问题呢？有两种可靠方案：

方案一

手写稳定排序。诸如冒泡排序，归并排序都是稳定的，你可以手写他们进行排序。当然 stl 自带的 stable_sort() 可能更方便……

方案二

多关键字排序。重写 cmp()，在你的程序中应将 cmp() 改成下面的形式：

bool cmp(node x, node y) {
    if (x.sum == y.sum)
        return x.rank < y.rank;
    return x.sum > y.sum;
}

......

for (int i = 0; i < n; i++) {
    cin >> a[i].n >> a[i].c >> a[i].m >> a[i].e;
    a[i].sum += a[i].c+a[i].m+a[i].e;
    a[i].rank = i;
}

这样就好了。

顺便说一下，我个人认为重载运算符实现排序会方便一些……

下面是我的 AC 代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1024;

struct student {
    string name;
    int chinese, math, english;
    int total, rank;
    bool operator < (const student &rhs) const {
        if (total == rhs.total)
            return rank < rhs.rank;
        return total > rhs.total;
    }
} s[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i].name;
        cin >> s[i].chinese >> s[i].math >> s[i].english;
        s[i].total = s[i].chinese + s[i].math + s[i].english;
        s[i].rank = i;
    }

    sort(s, s+n);
    cout << s[0].name << " " << s[0].chinese << " " << s[0].math << " " << s[0].english;

    return 0;
}

希望能帮到你！

by masonxiong @ 2024-02-01 20:35:17

@yucheng0630

cmp() 函数可以写得简单一些，虽然功能不变，如下：

bool cmp(stu x, stu y) {
    if (x.zf == y.zf)
        return x.id < y.id;
    return x.zf > y.zf;
}

或者，如果你会三元运算符的话，可以压到这样：

bool cmp(stu x, stu y) {
    return (x.zf == y.zf ? (x.id < y.id) : x.zf > y.zf);
}