题解 | #合并表记录 尝试不用stl容器完成#

尝试不用stl容器完成。还是c++容器好使。

#include <iostream>
using namespace std;

struct mp {
    int key;
    int value;
    void init(int a, int b) {
        key = a;
        value = b;
    }
};

int part(mp* r, int low, int high) {
    int i = low, j = high, pivot = r[low].key;
    while (i < j) {
        while (i < j && r[j].key > pivot) { //从右向左找一个小于等于pivot的数值
            j--;
        }
        if (i < j) {
            swap(r[i], r[j]);
            i++;
        }
        while (i < j && r[i].key <= pivot) {
            i++;
        }
        if (i < j) {
            swap(r[i], r[j]);
            j--;
        }
    }
    return i;
}

void quicsort(mp* r, int low, int high) {
    int mid;
    if (low < high) {
        mid = part(r, low, high);
        quicsort(r, low, mid - 1);
        quicsort(r, mid + 1, high);
    }
}

int main() {
    int num = 0;
    cin >> num;
    int a, b;
    mp m[num];
    for (int i = 0; i < num; i++) {
        cin >> a >> b;
        m[i].init(a, b);
    }
    quicsort(m, 0, num-1);//从小到大按key排序
    for(int i = 1;i<num;i++)
    {
        if(m[i].key==m[i-1].key)
        {
            m[i].value+=m[i-1].value;//本质合并相同key的value值
        }
    }
    for(int i=0;i<num;i++)
    {
        if(i+1==num)//防止越界
        {
            cout<<m[i].key<<' '<<m[i].value<<endl;
            break;
        }
        if(m[i].key==m[i+1].key){ continue;}
        else{cout<<m[i].key<<' '<<m[i].value<<endl;}
    }
}
// 64 位输出请用 printf("%lld")