1113 Integer Set Partition（25 分）

这个题目水成这个样子，，，

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int num[maxn], n;
int main()
{
    scanf("%d", &n);
    int sum = 0;
    for (int i = 0; i < n; i++)scanf("%d", &num[i]),sum += num[i];
    sort(num, num + n);
    int front = 0;
    for (int i = 0; i < n/2; i++)
    {
        front += num[i];
    }
    printf("%d %d",n%2==0?0:1, abs(sum - front - front));
    return 0;
}

算法笔记上有这个题目的解，作者用的是quick sort找出第n/2大的数字，然后分成两堆，但是这种有一个点会超时，我每次选的都是left

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int num[maxn], n;
int partition(int a[], int left, int right)
{
    int temp = a[left];
    while (left < right)
    {
        while (right > left&&a[right] > temp)right--;
        a[left] = a[right];
        while (left < right&&a[left] <= temp)left++;
        a[right] = a[left];
    }
    a[left] = temp;
    return left;
}
int main()
{
    scanf("%d", &n);
    int sum = 0;
    for (int i = 0; i < n; i++)scanf("%d", &num[i]),sum += num[i];
    int k = n / 2, left = 0, right = n - 1, mid;
    while (1)
    {
        int pos = partition(num, left, right);
        if (pos < k)left = pos + 1;
        else if (pos > k) right = pos - 1;
        else if (pos == k)
        {
            mid = pos;
            break;
        }
    }
    int front = 0;
    for (int i = 0; i < mid; i++)front += num[i];
    int back = sum - front;
    printf("%d %d", n % 2 == 0 ? 0 : 1, back - front);
    return 0;
}