题解 | 数组取精

/*
https://www.nowcoder.com/practice/6f77d207b40c41d899d23627d6bd122a?tpId=389&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D3%26subTabName%3Donline_coding_page&difficulty=3&judgeStatus=&tags=&title=&gioEnter=menu
*/

/*
解题思路
1.先将A和B两个数组分别进行降序排序(为了保证取出来的子集*2大于原来数组的和，从最大值开始取值)，
并且记录原来的索引位置；
复制一个新的数组A2和B2，记录原来的数据值和索引位置是否被选中；


2.
数组A：8 7 4 8 3
数组B：4 2 5 3 7

复制原数组A2和B2，再排序整理后

数组A
旧的索引位置: ④ ① ② ③ ⑤
数据值:       8 8 7 4 3
新的索引位置: ① ② ③ ④ ⑤

数组B
旧的索引位置: ⑤ ③ ① ④ ②
数据值:       7 4 5 3 2
新的索引位置: ① ② ③ ④ ⑤

遍历i~n数组排序后的A和B
 
第一种情况：如果排序后的A和B的索引位置相同，都为a_i，那么在A2和B2需要将A2[a_i]和B2[a_i]的index_flag标记为true，
			并且将A2[a_i]和B2[a_i]的值分别加到sum_a_p和sum_b_p中；
			将a_i的索引位置记录到index_p数组中，count + 1；

第二种情况：如果排序后的A和B的索引位置不同，分别为a_i和b_i，
			那么在A2和B2需要将A2[a_i]、A2[b_i]和B2[a_i]、B2[b_i]的index_flag标记为true，
			并且将A2[a_i]、A2[b_i]和B2[a_i]、B2[b_i]的值分别加到sum_a_p和sum_b_p中；
			将a_i和b_i的索引位置记录到index_p数组中，
			count + 2；

第三种情况：如果count == k_max - 1，说明已经选了k_max - 1个元素了，那么只能再选一个元素了，
			直接取排序后的A的第i个元素，记录索引位置a_i，
			将A2[a_i]和B2[a_i]的index_flag标记
			并且将A2[a_i]和B2[a_i]的值分别加到sum_a_p和sum_b_p中；
			将a_i的索引位置记录到index_p数组中，count + 1；
			

*/


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
	long long data_value;
	int index;
} Data_arr;


typedef struct {
	long long data_value;
	bool index_flag;
} Data_arr2;

/*降序*/
int compare_de(const void *a, const void *b)
{
    Data_arr *arr_a = (Data_arr *)a;
	Data_arr *arr_b = (Data_arr *)b;

    return arr_b->data_value - arr_a->data_value;
}

/*升序*/
int compare_in(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}


int main()
{
    int n;
	scanf("%d", &n);

	long long sum_a = 0, sum_b = 0;
	
	Data_arr *arr_A = (Data_arr *)malloc((n) * sizeof(Data_arr));
	Data_arr2 *arr_A2 = (Data_arr2 *)malloc((n) * sizeof(Data_arr2));

	Data_arr *arr_B = (Data_arr *)malloc((n) * sizeof(Data_arr));
	Data_arr2 *arr_B2 = (Data_arr2 *)malloc((n) * sizeof(Data_arr2));


	for (int i = 0; i < n; i++) {
	    scanf("%lld", &arr_A[i].data_value);
		arr_A[i].index = i;

		sum_a += arr_A[i].data_value;

		arr_A2[i].data_value = arr_A[i].data_value;
		arr_A2[i].index_flag = false;
	}

	qsort(arr_A, n, sizeof(Data_arr), compare_de);

	for (int i = 0; i < n; i++) {
	    scanf("%lld", &arr_B[i].data_value);
		arr_B[i].index = i;

		sum_b += arr_B[i].data_value;

		arr_B2[i].data_value = arr_B[i].data_value;
		arr_B2[i].index_flag = false;
	}
	qsort(arr_B, n, sizeof(Data_arr), compare_de);

	if(n==1)
	{
	    printf("1\n1\n");
		free(arr_A);
		free(arr_B);
		free(arr_A2);
		free(arr_B2);
		return 0;
	}

	int k_max = n/2 + 1;

	int *index_p = (int *)malloc((k_max) * sizeof(int));

	int count = 0;
	int flag = 0;

	while(flag == 0)
	{
		long long sum_a_p = 0;
		long long sum_b_p = 0;

		for (int i = 0; i < n; i++) 
		{
		    if((2*sum_a_p > sum_a) && (2*sum_b_p > sum_b))
			{
			    flag = 1;
				break;
			}
			else
			{
				if(!arr_A2[arr_A[i].index].index_flag && !arr_B2[arr_B[i].index].index_flag)
				{
					if(arr_A[i].index == arr_B[i].index)
					{
						index_p[count++] = arr_A[i].index + 1;

						sum_a_p += arr_A2[arr_A[i].index].data_value;
						sum_b_p += arr_B2[arr_B[i].index].data_value;

						arr_A2[arr_A[i].index].index_flag = true;
						arr_B2[arr_B[i].index].index_flag = true;
					
					}
					else if(count == k_max - 1)
					{
						index_p[count++] = arr_A[i].index + 1;

						sum_a_p += arr_A[i].data_value;
						sum_b_p += arr_B2[arr_A[i].index].data_value;

						arr_A2[arr_A[i].index].index_flag = true;
						arr_B2[arr_A[i].index].index_flag = true;
					}
					else
					{
						index_p[count++] = arr_A[i].index + 1;
						index_p[count++] = arr_B[i].index + 1;

						sum_a_p += arr_A[i].data_value + arr_A2[arr_B[i].index].data_value;
						sum_b_p += arr_B[i].data_value + arr_B2[arr_A[i].index].data_value;
						
						arr_A2[arr_B[i].index].index_flag = true;
						arr_B2[arr_A[i].index].index_flag = true;

						arr_A2[arr_A[i].index].index_flag = true;
						arr_B2[arr_B[i].index].index_flag = true;
					}
				}
			}
		}
	}

	printf("%d\n", count);

	qsort(index_p, count, sizeof(int), compare_in);

	for (int i = 0; i < count; i++) {
	    printf("%d ", index_p[i]);
	}

	free(arr_A);
	free(arr_B);
	free(arr_A2);
	free(arr_B2);
	free(index_p);

	return 0;
}