2019大疆笔试的一道编程题

/*
输入T，表示有几组书的方案
输入N，表示该方案有N本书
输入N行，每行有h书的厚度，w书的宽度
要求：书架下层只能将书竖着放（只计算h厚度），上层只能将书横着放（只计算宽度w）
求书架的最小宽度。
*/

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

struct Differs
{
    int differ;
    int index;
    Differs(int d, int i) : differ(d), index(i){}
};
bool comp(const Differs &a, const Differs &b)
{
    return a.differ < b.differ;
}

int getMax(int a, int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}
//N本书，h是厚度，w是宽度
int getMinWidth(int N, vector<int> &h, vector<int> &w)
{
    int sumh = 0, sumw = 0;
    int minW = 0;
    //一本书如果放下面，那么只把厚度h加到sumh，如果放上面，则只把w加到sumw
    //最后比较sumh和sumw，更小的就是答案。
    //对于一本书，h-w的差值越小，越要放到下面那一层，即加到sumh
    vector<Differs> differs;
    for (int i = 0; i < N; i++)
    {
        differs.push_back(Differs(h[i] - w[i], i));
        
    }
    sort(differs.begin(), differs.end(), comp);
    for (int i = 0; i < N; i++)
    {
        sumh = sumh + h[differs[i].index];
        sumw = 0;
        for (int j = i + 1; j < N; j++)
        {
            sumw = sumw + w[differs[j].index];
        }
        int min = getMax(sumh, sumw);
        if (0 == i)
        {
            minW = min;
        }
        if (min<minW)
        {
            minW = min;
        }
    }
    return minW;
}

int main()
{
    int T;
    cin >> T;
    vector<int> minW;
    //输入T组数据
    for (int i = 0; i < T; i++)
    {
        int N;  //N本书
        cin >> N;
        vector<int> h, w;
        for (int j = 0; j < N; j++)
        {
            int hj, wj;
            //输入N本书的厚度和宽度
            cin >> hj >> wj;
            h.push_back(hj);
            w.push_back(wj);
        }
        int minWi = getMinWidth(N, h, w);
        minW.push_back(minWi);
    }

    for (int i = 0; i < T; i++)
    {
        cout << "#Case " << i + 1 << ":" << minW[i] << endl;
    }
}