第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-998 娜神平衡

#include<stdio.h>
#include<math.h>
#include<stdbool.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
void shellSort(int *a, int len) ;
typedef long long ll;
int a[1005],val1[1005],val2[1005];
int n,r,tem,idx1,idx2;
void init(){
    memset(val1,0,sizeof(val1));
    memset(val2,0,sizeof(val2));
    idx1=idx2=0;
}
bool check(){
    int x=0,y=0,sum1=0,sum2=0,flag=1;
    sum1=val1[++x];
    while(abs(sum1-sum2)<=r&&flag){
        flag=0;
        if(abs(sum1+val1[x+1]-sum2)<=r&&x+1<=idx1){
            x++;
            flag=1;
            sum1+=val1[x];
        }
        if(abs(sum1-val2[y+1]-sum2)<=r&&y+1<=idx2){
            y++;
            flag=1;
            sum2+=val2[y];
        }
    }
    if(x==idx1&&y==idx2){
        return true;
    }
    else{
        return false;
    }
}
void print1(){
	int j;
    for( j=1;j<=idx1;j++){
            printf("%d ",val1[j]);
        }
    printf("\n");
}
void print2(){
	int j;
    for( j=1;j<=idx2;j++){
        printf("%d ",val2[j]);
    }
    printf("\n");
}
int main(){
	int i,j;
    scanf("%d%d",&n,&r);
    for( i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    tem=a[1];
    shellSort(a+1, n) ;
    for( i=0;i<(1<<n);i++){
        int judge=0;
        init();
        val1[++idx1]=a[1];
        for( j=1;j<n;j++){
            if((1<<j)&i){
                val1[++idx1]=a[j+1];
            }
            else{
                val2[++idx2]=a[j+1];
            }
        }
        if(check()){
            for( j=1;j<=idx1;j++){
                if(val1[j]==tem)
                    judge=1;
            }
            if(judge){
                print1();
                print2();
            }
            else{
                print2();
                print1();
            }
            break;
        }
    }
    return 0;
}
void shellSort(int *a, int len) {
	int i, j, k, tmp, gap;
	for (gap = len / 2; gap > 0; gap /= 2) {
		for (i = 0; i < gap; ++i) {
			for (j = i + gap; j < len; j += gap) {
				tmp = a[j];
				k = j - gap;
				while (k >= 0 && a[k] > tmp) {
					a[k + gap] = a[k];
					k -= gap;
				}
				a[k + gap] = tmp;
			}
		}
	}
}

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void output(vector<int> &A, int as)
{
	for(int i = 0; i < as; ++i)
	{
		cout << A[i] << (i == as-1 ? '\n' : ' ');
	}	
}

void f(vector<int> &v, vector<int> &A, vector<int> &B, int a, int b, int r, int n, vector<bool> &flag, bool &mark)
{
	int as = A.size();
	int bs = B.size();
	if(n == as + bs)
	{
		mark = false;
		sort(A.begin(), A.end());
		sort(B.begin(), B.end());
		output(A, as);
		output(B, bs);
		return;
	}
	
	for(int i = 0; i < n; ++i)
	{
		if(flag[i])
		{
			if(abs(a + v[i] - b) <= r)
			{
				A.push_back(v[i]);
				flag[i] = false;
				f(v, A, B, a+v[i], b, r, n, flag, mark);
				flag[i] = true;
				A.pop_back();
			}
			if(!mark) break;
			
			if(i > 0 && abs(b + v[i] - a) <= r)
			{
				B.push_back(v[i]);
				flag[i] = false;
				f(v, A, B, a, b+v[i], r, n, flag, mark);
				flag[i] = true;
				B.pop_back();
			}
			if(!mark) break;
		}
	}
	
}

int main()
{
	int n = -1;
	cin >> n;
	int r = -1;
	cin >> r;
	
	vector<int> v(n);
	for(int i = 0; i < n; ++i)
	{
		cin >> v[i];
	}
	
	vector<int> A;
	vector<int> B;
	vector<bool> flag(n, true);
	bool mark = true;
	
	f(v, A, B, 0, 0, r, n, flag, mark);
	
	return 0;
}

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
	// A B数组的下标
	static int idxa = 0, idxb = 0;
	static int[] A, B;
	static int r = 0;
	public static void main(String[] args) throws IOException {
		String[] in = reader.readLine().trim().split(" ");
		int n = Integer.parseInt(in[0]);
		r = Integer.parseInt(in[1]);
		int[] num = new int[n];
		in = reader.readLine().trim().split(" ");
		for (int i = 0; i < n; i++) {
			num[i] = Integer.parseInt(in[i]);
		}
		// 先记录下第一个数
		int first = num[0];
		Arrays.sort(num);
		// 状态搜索，n个数，用1表示在A数组中，用0表示在B数组中
		for (int i = 1; i < (1 << n) - 1; i++) {
			// 要排除全为0、全为1的情况
			idxa = 0;
			idxb = 0;
			A = new int[n];
			B = new int[n];
			for (int j = 0; j < n; j++) {
				// 当前位为1就存A
				if (((1 << j) & i) != 0) {  // 注意一定是不等于0，而不是一定等于1
					A[idxa++] = num[j];
				} else {
					B[idxb++] = num[j];
				}
			}
			// 每个数都放好位置了
			if (check()) {
				// 找存第一个数字的数组
				boolean is = false;
				for (int j = 0; j < idxa; j++) {
					if (A[j] == first) {
						is = true;
						break;
					}
				}
				if (is) {
					for (int j = 0; j < idxa; j++) {
						log.write(A[j] + " ");
					}
					log.write("\n");
					for (int j = 0; j < idxb; j++) {
						log.write(B[j] + " ");
					}
				} else {
					for (int j = 0; j < idxb; j++) {
						log.write(B[j] + " ");
					}
					log.write("\n");
					for (int j = 0; j < idxa; j++) {
						log.write(A[j] + " ");
					}
				}
				break;
			}
		}
		log.flush();
	}
	static boolean check() {
		int i = 0, j = 0, suma = 0, sumb = 0;
		// 按照题意，第一个数先放A数组
		suma += A[i++];
		boolean flag = true;
		while (Math.abs(suma - sumb) <= r) {
			flag = false;
			// 如果A中当前数可以放A，那就放A
			if (i < idxa && Math.abs(suma + A[i] - sumb) <= r) {
				suma += A[i++];
				flag = true;
			}
			// 如果B中当前数可以放B，那就放B
			if (j < idxb && Math.abs(suma - B[j] - sumb) <= r) {
				sumb += B[j++];
				flag = true;
			}
			if (flag == false) {
				break;
			}
		}
		if (i == idxa && j == idxb) return true;
		return false;
	}
}

import math
n, r = list(map(int, input().split()))
nums = list(map(int, input().split()))
global f1
f1 = nums[0]
nums.sort()

flag = 0

def dfs(a, b, step):
    global nums, flag
    if abs(sum(a) - sum(b)) > r and step == 1:
        pass
    elif abs(sum(a) - sum(b)) > r:
        return
    if len(nums) == 0:
        flag = 1
        a.sort()
        b.sort()
        if f1 in a:
            for i in a:
                print(i, end=' ')
            print()
            for j in b:
                print(j, end=' ')
        if f1 in b:
            for i in b:
                print(i, end=' ')
            print()
            for j in a:
                print(j, end=' ')

        return
    for i in range(len(nums)):
        a.append(nums[i])
        nums.pop(i)
        dfs(a, b, step + 1)
        if flag == 1:
            return
        nums.insert(i, a.pop())
    for i in range(len(nums)):
        b.append(nums[i])
        nums.pop(i)
        dfs(a, b, step + 1)
        if flag == 1:
            return
        nums.insert(i, b.pop())


dfs([], [], 0)