题4

题4

题目

【2016 统考真题】已知由 ( ) 个正整数构成的集合 ,将其划分为两个不相交的子集 和 ,元素个数分别是 和 和 中的元素之和分别为 和 。
设计一个尽可能高效的划分算法,满足 最小且 最大。要求:

1. 给出算法的基本设计思想。
2. 根据设计思想, 采用 C 或 C++语言描述算法, 关键之处给出注释。
3. 说明所设计算法的平均时间复杂度和空间复杂度。

分析

首先解决子集内元素求和的函数，考虑直接挨个遍历元素求和
再来考虑划分问题，直接暴力循环，设置一个gap作为两个子集数量之差的绝对值，让的从0开始，的数量就是
直到取，记录每一次循环的gap到数组里，还有求和的结果，每次如果满足，gap更小同时子集求和的差最大，就保存这对划分，还有gap和的值
时间复杂度上，因为两层循环，内层n，外层也是n，总的就是
空间复杂度上，因为开了3个为n的数组，所以是

解

#include<bits/stdc++.h>
using namespace std;
 
const int N = 100000;
 
int big[N],a1[N],a2[N];
 
int n = 0;
 
int ds = 0; //s1-s2
int res_a1[N]; //划分的结果a1
int res_a2[N]; //划分的结果a2
int gap = 0x7fffffff;
 
int sum(int a*, int head, int end) {
	int sum_res = 0;
	for (int i = head; i < end; i++) {
    sum_res += a[i];
  }
    return sum_res;
}
 
int main() {
	cin >> n;
	for(int i = 0 ;i<n;i++) {
		cin >> big[i];
	}
	for(int i =2; i<n;i++) {
		int n1 = i, n2 = n-i;
		int sum_a1 = sum(int big*, 0, n1);
		int sum_a2 = sum(int big*, n1, n);
	    int gap_temp = abs(n1-n2);
        
        if(gap_temp < gap) { //如果gap更小
        //同时s1-s2的绝对值更大
			if(abs(sum_a1-sum_a2) > ds) {
				gap = gap_temp;
				ds = abs(sum_a1-sum_a2);
				for(int j = 0; j<n1;j++) {
						res_a1[j] = big[j];
				}
				for(int j = 0; j<n2;j++) {
						res_a2[j] = big[j+n1];
				}
		}
	}
	//最后输出保存的两个子集，还有gap和s1-s2的值
	for(int i = 0; i<n1;i++) {
    cout << res_a1[i] << " ";
  }
    cout << endl;
      for(int i = 0; i<n2;i++) {
      cout << res_a2[i] << " ";
  }
    cout << endl;
    cout << gap << " " << ds << endl;
    return 0;
}