算法期中练习——1000.分组

算法期中练习——1000.分组

Description:

对于一个整数数列A[0], A[1], …, A[N-1]进行分组，要求每组1到2个数，并且同组之和不能大于w. 求最少可以分成多少组.
1 <= N <= 100000, 1 <= A[i] <= w <= 1000000000.

Example:

例1：当A = {2, 5, 4, 3}, w = 5, minPartition(A, w)返回3. 将2和3放一组，4和5各自单独作为一组，共3组.

例2：当A = {2, 5, 4, 3}, w = 7, minPartition(A, w)返回2. 将2和5放一组，3和4一组，共2组.

请实现下面Solution类中计算minPartition(A, w)的函数.

class Solution {
public:
       int minPartition(vector<int> A, int w) {
             
       }
};

---

分析：

首先利用sort函数给输入的数组按从小到大排序；
因为w不会比数组中的数小，且要求分组，组中任意1个或2个之和不大于w，因此很容易想到让最小的和最大的数相加，判断两者之和与w的大小，从而更新比较的数的下标。

代码如下：

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

class Solution {
public:
    int minPartition(vector<int> A, int w) {
        sort(A.begin(), A.end());
        int num = 0;
        int temp = 0;
        int i = 0, j = A.size() - 1;
        while (i <= j && j >= 0) {
        	temp = A[i] + A[j];
        	if (temp > w) {
        		j--;      		
        	} else {
        		i++;
        		j--;
			}
        	num++;
        	temp = 0;
        }
        return num;
    }
};
// another solution
class Solution {
public:
	int minPartition(vector<int> A, int w) {
		int res, n, i, j;
		n = A.size();
		sort(A.begin(), A.end());
		res = 0;
		for (i = 0, j = n - 1; i <= j; j--) {
			if (A[i] + A[j] <= w) i++;
			res++;
		}
		return res;
	}
};
int main() {
    Solution s;
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    int w;
    cin >> w;
    cout << s.minPartition(A, w) << endl;
    return 0;
}