题解 | #合并表记录#

#include #include using namespace std; const int N = 13390; int q[N]; int idx[N]; void quick_sort(int idx[], int l, int r) {//直接快排模板 if (l >= r) return; int i = l - 1, j = r + 1; int x = idx[(l + r) / 2]; while (i < j) { do i++; while (idx[i] < x); do j--; while (idx[j] > x); if (i < j) swap(idx[i], idx[j]); } quick_sort(idx, l, j); quick_sort(idx, j + 1, r);

} int main() { int n; int k = 0;

cin >> n;
int bi = n;


memset(q, 0, sizeof q);
while (n--) {//这里n的值在自减，快排时用到元素个数，用bi保存元素个数
    int a;
    long int b;
    cin >> a >> b;
    q[a%13331] += b;//编号相同元素的放入同一个位置，累加求和,这里采用哈辛映射，直接映射的话，会爆内存，取13331属于经验值
    idx[k++] = a;//编号存入数组，搞个快排！
}
quick_sort(idx, 0, bi - 1);
for (int i = 0; i < bi; i++) {
    if (idx[i + 1] == idx[i]) continue;
    printf("%d ", idx[i]);
    cout << q[idx[i] % 13331] << endl;
}

return 0;

}