高考成绩

发表于 | 更新于 | 分类于

题目链接： 高考排名

审题发现，如果使用直接搜索肯定会超时，循环次数太多，所以不考虑。确定使用 lower_bound + 结构体来完成题目。具体思路也没问题，但是第一遍（ cin 读入数据）做的时候死活过不了。。。 然后想了想，应该是数据太大吧，使用 scanf 来读入，又发现 string 必须改为 char 数组才能被读入，有重写了比较函数。整了很久才整完~呼
结果第二天，候代轩同学意外的将考好使用 int 来存储，然后就ac了，当时整个人都傻掉了，题目没有要求输出考号信息呀，前置零丢了就丢呗！(重点是审题)
后几天，想了想，还是应该用 string 来存储考号，确保信息完整，但是对于这道题目，使用 int 也可以了，所以，最后将两种做法都公布出来。。

第一种 int 考号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
struct info {
    string name;
    int kh;
    int s;
    int rank;
};
info a[100005];
bool cmp1(info a,info b){
    return a.s>b.s;
} 
bool cmp2(info a,info b){
    return a.kh>b.kh;
}

int main(void)
{                    
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].kh>>a[i].name>>a[i].s;
    }
    sort(a+1,a+1+n,cmp1);
    int r=1;
    a[1].rank=1;
    for(int i=2;i<=n;i++)       //按照成绩来排名，成绩相同的排名不变                   
    {
        if(a[i-1].s!=a[i].s)
        {
            r++;
            a[i].rank=r;
        }
        else
        {
            a[i].rank=r;
        }
    }
    sort(a+1,a+1+n,cmp2);
    int m;
    cin>>m;
    info f;                                 //结构体f,用来lower_bound查找
    for(int i=1;i<=m;i++)
    {
        cin>>f.kh;
        int ans=lower_bound(a+1,a+1+n,f,cmp2)-a; 
        if(ans<n+1&&a[ans].kh==f.kh)    //如果返回值小于n+1并且两者的考号相同则表示查找到了结果
        {
            cout<<a[ans].name<<" "<<a[ans].rank;
        }
        else
        {
            cout<<"Test error number!";
        }
        cout<<'\n';
    }
    return 0;
}

第二种 stirng 考号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

struct info
{
	char kh[8];    //学生考号
	char name[12]; //学生姓名
	int s;         //学生成绩
	int rank;      //学生名次
}a[100005];

bool cmp1(info a, info b)  //第一遍按照成绩排
{
	return a.s > b.s;
}
bool cmp2(info a, info b)  //第二遍按照考号排
{
	if(strcmp(a.kh, b.kh) >= 0)
	{
		return false;
	}
	if(strcmp(a.kh,b.kh) < 0)
	{
		return true;
	}
}

int main(void)
{
	int n;
	scanf("%d",&n);

	for(int i=1; i<=n; i++)
	{
		scanf("%s%s%d",&a[i].kh, &a[i].name, &a[i].s);
	}

	sort(a+1,a+1+n,cmp1);

	int r=1;               //如果两个学生成绩相等，则同一名次，否则名次+1.
	a[1].rank = 1;
	for(int i=2; i<=n; i++)
	{
		if(a[i-1].s!=a[i].s)
		{
			r++;
			a[i].rank = r;
		}
		else
		{
			a[i].rank = r;
		}
	}
	sort(a+1,a+1+n,cmp2);

	int m;
	cin >> m;
	info f;
	for(int i=1; i<=m; i++)
	{
		cin>>f.kh;
		int ans=lower_bound(a+1,a+1+n,f,cmp2)-a;  //利用lower_bound找到学号相同的（刚才cmp没写相等，所以一直找不到相等的），输出名字和成绩。

		if(strcmp(a[ans].kh,f.kh)==0 && ans < n+1 )
		{
			printf("%s %d\n", a[ans].name, a[ans].rank);
		}
		else
		{
			printf("Test error number!\n");
		}
	}
	return 0;
	}

总结，这种题目一般来讲不难，重点是抓住题目核心，能够灵活的使用 lower_bound ,尤其是特判 if(ans<n+1&&a[ans].kh==f.kh) ！！！