题目描述
blablabla
样例
blablabla
算法1
(二分)
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 60010;
int grade[N];
int index1, index2;
struct person
{
string id;
int pos, rk1, rk2, score;
}p[N];
int cmp(int a, int b) {
return a > b;
}
int cmp1(person a, person b) {
if (a.rk2 != b.rk2) return a.rk2 < b.rk2;
else return a.id < b.id;
}
int get_rk(int l, int r, int score) {
while (l < r) {
int mid = (l + r) >> 1;
if (grade[mid] > score) l = mid + 1;
else r = mid;
}
return l + 1 - index1;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int m, score;
string id;
cin >> m;
while (m--)
{
cin >> id >> score;
person p1;
p1.id = id;
p1.pos = i;
p1.score = score;
grade[index2] = score;
p[index2++] = p1;
}
sort(grade + index1, grade + index2, cmp);
for (int j = index1; j < index2; j++)
{
p[j].rk1 = get_rk(index1, index2, p[j].score);
}
index1 = index2;
}
sort(grade, grade + index2, cmp);
for (int j = 0; j < index2; j++) {
p[j].rk2 = get_rk(0, index2, p[j].score) + index1;
}
sort(p, p + index2, cmp1);
cout << index2 << endl;
for (int j = 0; j < index2; j++) {
cout << p[j].id << " " << p[j].rk2 << " " << p[j].pos << " " << p[j].rk1 << endl;
}
}