80分求助

P1093 [NOIP2007 普及组] 奖学金

樱雪喵 @ 2020-01-12 16:22:48

测试点1,2WA了。。。

#include <bits/stdc++.h>
using namespace std;
int n,a[301],b[301],c[301],num[301],d[301];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i];
        d[i]=a[i]+b[i]+c[i];
        num[i]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<n-i;j++){
            if(d[j]<d[j+1]){
                swap(d[j],d[j+1]);
                swap(a[j],a[j+1]);
                swap(num[j],num[j+1]);
            }
            if(d[j]==d[j+1]&&a[j]<a[j+1]){
                swap(d[j],d[j+1]);
                swap(a[j],a[j+1]);
                swap(num[j],num[j+1]);
            }
            if(d[j]==d[j+1]&&a[j]==a[j+1]&&num[j]>num[j+1]){
                swap(d[j],d[j+1]);
                swap(a[j],a[j+1]);
                swap(num[j],num[j+1]);
            }
        }
    }
    for(int i=1;i<=5;i++) cout<<num[i]<<" "<<d[i]<<endl;
    return 0;
}

by DOs__lx @ 2020-01-28 13:30:29

可以用sort,代码仅供参考

#include<iostream>
#include<cstdio>
#include<algorithm>
#define M 305
using namespace std;
struct fenshu{
    int ch,ma,en,numm;
    int sum;
};
fenshu p[M];
int n;
bool cmp(const fenshu a,const fenshu b){
    if(a.sum!=b.sum) return a.sum>b.sum;
    else if(a.ch!=b.ch) return a.ch>b.ch;
    else return a.numm<b.numm;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&p[i].ch,&p[i].ma,&p[i].en);
        p[i].numm=i;;
        p[i].sum=p[i].ch+p[i].ma+p[i].en;
    }
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=5;++i)
        cout<<p[i].numm<<" "<<p[i].sum<<endl;
    return 0;
}

by DOs__lx @ 2020-01-28 13:33:40

加一个cmp函数作为sort的第三个参数会方便很多,如果用冒泡可能没有办法处理相等的情况,sort还比较简洁,偏爱短代码当然,用sort肯定用结构体更方便


by FishingStar @ 2020-01-31 11:21:59

手写sort函数

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
using namespace std;

void sort(vector<long long> &a, int left, int right){
    if(left >= right){
        return;
    }
    int i = left, j = right;
    long long key = a[j];
    while(i < j){
        while(a[i] >= key && i < j){
            i++;
        }
        a[j] = a[i];
        while(a[j] <= key && i < j){
            j--;
        }
        a[i] = a[j];
    }
    a[j] = key;
    sort(a, left, j - 1);
    sort(a, j + 1, right);
    return;
}
int main(){
    vector<long long> a(305);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        a[i] = 300 - i + 1000 * x + 1000000 * (x + y + z);  
    }
    sort(a, 0, n - 1);
    for(int i = 0; i < 5; i++){
        cout << 300 - a[i] % 1000 + 1 << " " << a[i] / 1000000 << endl;
    }
    return 0;
}

|