데이터 구조 기록 - 종합 평가 성적 정렬

Home
Web Board
ProblemSet
Standing
Status
Statistics
문제 F: 종합 평가 성적 정렬
Time Limit: 1 Sec  
Memory Limit: 128 MB
Submit: 1034  
Solved: 160
[ Submit][ Status][ Web Board]
Description
한 반 학생 들 의 종합 평가 성적 (수학, 영어, 정치 세 과목, 학점, 가중치 등 정보 포함) 을 계산 하고 학생 들 의 종합 평가 성적 에 따라 순 위 를 매 긴 다.
Input
여러 그룹의 데 이 터 를 포함 하여 각 그룹의 데이터 의 첫 줄 은 하나의 정수 n (n < 50000) 으로 몇 명의 학생 이 있 는 지 표시 합 니 다.다음 n + 1 줄, 첫 번 째 줄 은 세 개의 실수 (0 에서 1 사이) 로 입력 하고 각각 3 과 성적 이 종합 평가 에서 차지 하 는 가중치 를 대표 한다.그 다음 에 입력 한 n 줄 은 한 학생 을 대표 하고 각 줄 은 이름 (주: 이름 은 알파벳 과 밑줄 만 포함 하고 25 자 를 초과 하지 않 음), 국어, 수학, 영어 세 과목 의 성적 (주: 성적 은 실수 이 고 0 에서 100 사이), 종합 평가 성적 은 모든 과목 의 점수 와 가중 과 이다.
Output
각 조 의 데이터 에 대해 종합 평가 성적 순 위 는 높 은 것 에서 낮은 것 으로 모든 학생 (성적 은 똑 같이 성명 사전 순 으로 배열) 을 수출 하고 각 줄 은 이름, 국어, 수학, 영어 세 과목 의 성적, 종합 평가 점 수 는 구체 적 으로 사례 를 볼 수 있다.
Sample Input
10.5 0.5 0.5zhangsan 100 100 10030.2 0.3 0.6zhangsan 100 20 50lisi 55 66 77wangwu 22 33 66
Sample Output
zhangsan 100.0 100.0 100.0 150.0lisi 55.0 66.0 77.0 77.0zhangsan 100.0 20.0 50.0 56.0wangwu 22.0 33.0 66.0 53.9
HINT
고찰 지식 점: 작은 데이터 양의 정렬 문제, 시간 복잡 도 O (nlog), 공간 복잡 도 O (n)
라 이브 러 리 함수 정렬 사용 안 함
Append Code
[ Submit][ Status][ Web Board]

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef struct
{
    string name;
    double chinese,math,english,sum;
} student;
void Qst(student *s,int low,int high)
{
    int x=low;
    int y=high;
    student st=s[low];
    if(low >= high)
    {
        return;
    }
    while(x<y)
    {
        while(x<y&&s[y].sum>=st.sum)
        {
            if(s[y].sum== st.sum&&s[y].name>= st.name)
                break;
            --y;
        }
        s[x]=s[y];
        while(x < y && s[x].sum<=st.sum)
        {
            if(s[x].sum== st.sum&&s[x].name<= st.name)
                break;
            ++x;
        }
        s[y]=s[x];
    }
    s[x]=st;
    Qst(s,low,x-1);
    Qst(s,x+1,high);
}
int main()
{
    int n,i;
    string name;
    double a,b,c;
    while(cin>>n>>a>>b>>c)
    {
        student s[n];
        for(i=0; i<n; i++)
        {
            cin>>s[i].name>>s[i].chinese>>s[i].math>>s[i].english;
            s[i].sum=0;
            s[i].sum+=s[i].chinese*a;
            s[i].sum+=s[i].math*b;
            s[i].sum+=s[i].english*c;
        }
        Qst(s,0,n-1);
        for(i=n-1; i>=0; i--)
        {
            cout<<s[i].name<<" ";
            printf("%.1lf %.1lf %.1lf %.1lf
",s[i].chinese,s[i].math,s[i].english,s[i].sum);
        }
    }
}