Question

C++程序题结构体和sort排序问题E：进步最快

问题 E: 进步最快

时间限制: 1 Sec 内存限制: 128 MB 提交: 20 解决: 0
[提交][状态][讨论版]
题目描述

现在中学的学习竞争十分激烈，每次考试之后，整个年级都会排名，甚至连学号都会根据成绩排名，进行重新编号。这样的学号编排，能马上看出学生的成绩情况。若出现成绩相同，那么，就按照上次考试成绩排序，也就是当前学号从小到大排。因为，不可能产生相同的新学号。现在，此次考试的成绩已经批改统计完成，老师想要表彰进步最快的同学，也就是名次上升最多的同学，那么请你帮老师写个程序找出这位进步最快的同学吧！
输入

第一行一个整数n，表示学生总数。

第二行n个整数，表示每个学生的成绩，给出的顺序就是按照学号顺序即第一个数是1号同学的成绩，第二个数是2号同学的成绩，以此类推。

10 ≤ n ≤ 100,000，每个人的成绩都在0~100范围内。
输出

根据成绩，对学号进行重新编号。第一行输出新编号中上升幅度最大的同学的编号（注意，是新的编号！）。

若两位同学名次上升幅度相同，输出名次靠前的，也就是编号较小的。帮老师找出这位进步最快的同学进行表彰！

第二行输出该同学之前的学号。
样例输入

样例输入1：
5
95 96 97 98 99

样例输入2：
5
100 98 99 96 97

样例输出

样例输出1：
1
5

样例输出2：
2
3

提示

【数据规模】
20%数据：n ≤ 100。
50%数据：n ≤ 1,000。
100%数据：n ≤ 100,000。

Answer 1

我平时有刷类似算法题，如图leetcode上我的记录。此题的思想很简单:原编号就是原排名，自己写个比较函数用sort进行索引排序！这样就能轻松比较排名变化。

程序如下，有详细注释

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef union G_sort{
	char grade[4];
	int id;
}G_sort;
bool greater(const G_sort &a, const G_sort &b) {
	return a.grade[3] > b.grade[3];	//成绩(高8位)
}
int main() {
	//输入
	int n;	cin >> n;	//第一行一个整数n，表示学生总数。
	vector<G_sort> grade(n);	//表示每个学生的  编号(高24位)|成绩(低8位)
	for (int i = 0; i < n; i++) {	//n ≤ 100, 000
		scanf("%d", &grade[i].grade[3]);	//成绩(高8位)
		//cin >> grade[i].grade[3];	★这种输入会出错
		grade[i].id |= i;	//编号(低24位)
	}
	//排序
	sort(grade.begin(), grade.end(), greater);	//根据学号排序
	int d_sort = 0, now_sort;//排名上升多少，现排名
	for (int i = 0; i < n; i++) {
		int d = (grade[i].id & 0xffffff) - i;	//原排名-现排名
		if (d > d_sort) {	//若两位同学名次上升幅度相同，输出名次靠前的，也就是编号较小的。（不能取=）
			d_sort = d;
			now_sort = i + 1;	//注意！下标从0数起 比排名少1
		}
	}
	//输出
	/*
	 //16进制查看 grade 数据
	for (int i = 0; i < n; i++) {
		printf("%x\n", grade[i].id);
	}*/
	cout << now_sort << endl << now_sort+ d_sort << endl;
	system("pause");
	return 0;
}

追答

我用了共用体来节省空间(我其实是电子本科，所以编单片机很擅长用共用体)

如果搞不清楚共用体，可以还改用结构体哈。

如下是采用结构体的正常写法！建议推荐此写法，上面那种是“强迫症”写法，不建议学。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef struct G_sort{
int grade;
int id; //编号-1（从0数起）
}G_sort;
bool greater(const G_sort &a, const G_sort &b) {
return a.grade > b.grade; //成绩(高8位)
}
int main() {
//输入
int n; cin >> n; //第一行一个整数n，表示学生总数。
vector<G_sort> grade(n); //表示每个学生的  编号(高24位)|成绩(低8位)
for (int i = 0; i < n; i++) { //n ≤ 100, 000
cin >> grade[i].grade; //成绩
grade[i].id = i; //编号
}
//排序
sort(grade.begin(), grade.end(), greater); //根据学号排序
int d_sort = 0, now_sort;//排名上升多少，现排名
for (int i = 0; i < n; i++) {
int d = grade[i].id - i; //原排名-现排名
if (d > d_sort) { //若两位同学名次上升幅度相同，输出名次靠前的，也就是编号较小的。（不能取=）
d_sort = d;
now_sort = i + 1; //注意！下标从0数起 比排名少1
}
}
//输出
cout << now_sort << endl << now_sort+ d_sort << endl;
system("pause");
return 0;
}

有什么疑问请追问！

代码只能在网页端可见。
如果觉得答案满意请采纳。无论你采纳与否，提问的财富值都已经扣掉了的，脑力劳动也需要被尊重。

Answer 2

你都已经知道用什么做了唉

#include<bits/stdc++.h>
using namespace std;
struct students{
	int old_num;
	int new_num;
	int up;
	int grade;
}stu[100003];
bool cmp(students a,students b)
{
	if(a.grade>b.grade) return true;
	else return false;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>stu[i].grade;
		stu[i].old_num=i;
	}
	sort(stu+1,stu+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		stu[i].new_num=i;
		stu[i].up=stu[i].new_num-stu[i].old_num;
	}
	int ans_up=0x7f7f7f7f;//inf
	int ans_num=0x7f7f7f7f;//inf
	int tik=0x7f7f7f7f;
	for(int i=1;i<=n;i++)
	{
		if(stu[i].up<ans_up)
			if(stu[i].new_num<ans_num)
				ans_up=stu[i].up,tik=i;
	}
	cout<<stu[tik].new_num<<endl<<stu[tik].old_num;
	return 0;
}

追问

那具体是什么步骤呢，可不可以给解释一下，本人刚学编程，没太看懂什么意思