题解 | #合并表记录#

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct table {
    int index;
    int value;
};

int main() {
    int n;
    //  输入个数
    cin >> n;
    vector<table> arr;
    arr.resize(n);
    vector<table>::iterator iter;
    //  输入内容
    for (iter = arr.begin(); n > 0; --n, ++iter) {
        cin >> (*iter).index;
        cin >> (*iter).value;
    }
    vector<table>::iterator iter2;
    //  合并，双指针，后指针遍历余下内容，若后面的索引和前面的相等了，则进行合并
    for (iter = arr.begin(); iter != arr.end(); ++iter) {
        for (iter2 = iter + 1; iter2 != arr.end(); ++iter2) {
            if ((*iter).index == (*iter2).index) {
                (*iter).value += (*iter2).value;
                arr.erase(iter2);
                --iter2;
            }
        }
    }

    //  排序，不排序不算正确，试过了，这个地方用的是冒泡，想降低时间复杂度可以试试快排
  	//	尝试过直接用sort，但是不行，编译错误
    for (iter = arr.begin(); iter != arr.end(); ++iter) {
        for (iter2 = iter + 1; iter2 != arr.end(); ++iter2) {
            if ((*iter).index > (*iter2).index) {
                swap(*iter, *iter2);
            }
        }
    }

  	//	输出
    for (iter = arr.begin(); iter != arr.end(); ++iter) {
        cout << (*iter).index << ' ' << (*iter).value << endl;
    }
}
// 64 位输出请用 printf("%lld")