C++奥赛一本通刷题记录(排序)

C++奥赛一本通刷题记录(排序)

2017.11.16 By gwj1139177410

都是拿STL水的…别怪我……

  1. 谁考了第k名 openjudge01

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn = 110;
    struct node{ int id; float score; }a[maxn];
    int cmp(node a, node b){ return a.score==b.score?a.id<b.id:a.score>b.score; }
    int main(){
    int n, k; cin>>n>>k;
    for(int i = 0; i < n; i++)cin>>a[i].id>>a[i].score;
    sort(a,a+n,cmp);
    cout<<a[k-1].id<<" "<<a[k-1].score<<"\n";
    return 0;
    }
  2. 奇数单增序列 openjudge02

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn = 550;
    int n, a[maxn];
    int main(){
    int t; cin>>t;
    while(t--){
    cin>>a[n];
    if(a[n]%2==1)n++;
    }
    sort(a,a+n);
    for(int i = 0; i < n-1; i++)cout<<a[i]<<",";
    cout<<a[n-1]<<"\n";
    return 0;
    }
  3. 成绩排序 openjudge03

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include<iostream>
    #include<algorithm>
    #include<string>
    using namespace std;
    const int maxn = 110;
    struct node{ string name; int score; }a[maxn];
    int cmp(node a, node b){ return a.score==b.score?a.name<b.name:a.score>b.score; }
    int main(){
    int n; cin>>n;
    for(int i = 0; i < n; i++)cin>>a[i].name>>a[i].score;
    sort(a,a+n,cmp);
    for(int i = 0; i < n; i++)cout<<a[i].name<<" "<<a[i].score<<"\n";
    return 0;
    }
  4. 奖学金 openjudge04

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    #include<iostream>
    #include<algorithm>
    #include<string>
    using namespace std;
    const int maxn = 310;
    struct node{ int id, score, chinese; }a[maxn];
    int cmp(node a, node b){
    if(a.score != b.score)return a.score>b.score;
    if(a.chinese != b.chinese)return a.chinese>b.chinese;
    return a.id<b.id;
    }
    int main(){
    int n; cin>>n;
    for(int i = 0; i < n; i++){
    int x,y,z; cin>>x>>y>>z;
    a[i].id=i+1; a[i].chinese=x; a[i].score=x+y+z;
    }
    sort(a,a+n,cmp);
    for(int i = 0; i < 5; i++)cout<<a[i].id<<" "<<a[i].score<<"\n";
    return 0;
    }
  5. 分数线划定 openjudge05

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #include<iostream>
    #include<algorithm>
    #include<string>
    using namespace std;
    const int maxn = 5050;
    struct node{ int id, score; }a[maxn];
    int cmp(node a, node b){
    if(a.score != b.score)return a.score>b.score;
    return a.id<b.id;
    }
    int main(){
    int n, m; cin>>n>>m; m=m*1.5;
    for(int i = 1; i <= n; i++)
    cin>>a[i].id>>a[i].score;
    sort(a+1,a+n+1,cmp);
    for(int i = m+1; i <= n; i++)
    if(a[i].score==a[m].score)m++;
    cout<<a[m].score<<" "<<m<<"\n";
    for(int i = 1; i <= m; i++)
    cout<<a[i].id<<" "<<a[i].score<<"\n";
    return 0;
    }
  6. 整数奇偶排序 openjudge06

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #include<iostream>
    #include<algorithm>
    #include<string>
    using namespace std;
    const int maxn = 20;
    int a[maxn], b[maxn], an, bn;
    bool cmp(int a, int b){return a>b;}
    int main(){
    for(int i = 1; i <= 10; i++){
    int x; cin>>x;
    if(x%2==1)a[an++]=x;
    else b[bn++]=x;
    }
    sort(a,a+an,cmp);
    sort(b,b+bn);
    for(int i = 0; i < an; i++)cout<<a[i]<<" ";
    for(int i = 0; i < bn; i++)cout<<b[i]<<" ";
    return 0;
    }
  7. 合影效果 openjudge07

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    using namespace std;
    const int maxn = 50;
    int an, bn;
    float a[maxn], b[maxn];
    bool cmp(float a, float b){return a>b;}
    int main(){
    int n; cin>>n;
    for(int i = 1; i <= n; i++){
    string s; cin>>s;
    float x; cin>>x;
    if(s[0]=='m')a[an++]=x;
    else b[bn++]=x;
    }
    sort(a,a+an);
    sort(b,b+bn,cmp);
    for(int i = 0; i < an; i++)printf("%.2f ", a[i]);
    for(int i = 0; i < bn; i++)printf("%.2f ", b[i]);
    return 0;
    }
  8. 病人排队 openjudge08

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #include<iostream>
    #include<algorithm>
    #include<string>
    using namespace std;
    const int maxn = 110;
    int an, bn;
    struct node{ string id; int age, que; }a[maxn], b[maxn];
    bool cmp1(node a, node b){ return a.age!=b.age?a.age>b.age:a.que<b.que; }
    bool cmp2(node a, node b){ return a.que<b.que; }
    int main(){
    int n; cin>>n;
    for(int i = 1; i <= n; i++){
    string s; int x; cin>>s>>x;
    if(x>=60){ a[an].id=s; a[an].que=i; a[an++].age=x; }
    else { b[bn].id=s; b[bn].que=i; b[bn++].age=x; }
    }
    sort(a,a+an,cmp1);
    sort(b,b+bn,cmp2);
    for(int i = 0; i < an; i++)cout<<a[i].id<<"\n";
    for(int i = 0; i < bn; i++)cout<<b[i].id<<"\n";
    return 0;
    }
  9. 明明的随机数 openjudge09

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn = 110;
    int a[maxn];
    int main(){
    int n; cin>>n;
    for(int i = 0; i < n; i++)cin>>a[i];
    sort(a,a+n);
    n = unique(a,a+n)-a;
    cout<<n<<"\n";
    for(int i = 0; i < n; i++)cout<<a[i]<<" ";
    return 0;
    }
  10. 单词排序 openjudge10

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #include<iostream>
    #include<algorithm>
    #include<string>
    #include<sstream>
    using namespace std;
    const int maxn = 110;
    string a[maxn];
    int main(){
    string s; getline(cin,s);
    int n = 0;
    stringstream ss(s);
    while(ss>>a[n])n++;
    sort(a,a+n);
    n = unique(a,a+n)-a;
    for(int i = 0; i < n; i++)cout<<a[i]<<"\n";
    return 0;
    }
  11. 出现次数超过一半的数 openjudge28

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //垃圾题目,浪费我一节课,我TM就桶排序了,你来打我啊
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n, a[1010];
    int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
    int x; cin>>x; a[x+100]++;
    }
    int t=0, tt=0;
    for(int i = 1; i <= 200; i++)
    if(a[i]>tt){ t=i; tt=a[i]; }
    if(tt>n/2)cout<<t-100<<"\n";else cout<<"no\n";
    return 0;
    }
  12. 统计字符数 openjudge29

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include<iostream>
    #include<string>
    using namespace std;
    int a[40];
    int main(){
    string s; getline(cin,s);
    for(int i = 0; i < s.size(); i++)a[s[i]-'a']++;
    int t=0, tt=0;
    for(int i = 0; i < 40; i++)
    if(a[i]>tt){ t=i; tt=a[i]; }
    cout<<(char)('a'+t)<<" "<<tt<<"\n";
    return 0;
    }