题目

给定n个棍子的长度和整数k，求能否在其中选出2k个棍子拼成两个凸多边形。使得两个凸多边形都恰好有k跟棍子组成,且任意相邻的边都不共线。

输入

第一行包括两个正整数n,k，表示棍子总数和多边形边数。
第二行包括n个正整数，表示每根棍子的长度。

输出

第一行输出一个单词Yes或者No表示是否能选出满足要求的2k个棍子。
如果第一行输出的是Yes,则第二行要输出方案。输入的棍子从1开始按照输入顺序编号，你需要输出2k个空格隔开的正整数，前k个表示组成第一个凸多边形的棍子的编号，后k个表示组成第二个凸多边形棍子的编号。
如果有多种方案，输出任意一种即可。

样例

样例输入
Input 1:
6 3
1 1 1 2 2 2

Input 2:
6 3
1 2 3 100 200 300

样例输出
Output 1:
Yes
1 2 3 4 5 6

Output 2:
No

题解

凸多边形判断条件：其中最大的边的长度小于其余所有边的总和
对边的长度从大到小排序后，其中有间断的序列符合条件就一定有连续的序列符合条件（证明略）
所以此题排序后分为两种情况：
a、有两块连续的长度为k的序列（前缀和枚举）
b、有一块长度为2k的序列，但是里面子序列的顺序比一定连续（dfs搜索）

AC代码

#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long 
const int N = 1e3 + 15;
struct Edge {
	ll val;
	int p;
}edge[N];
bool cmp(Edge e1, Edge e2) {
	return e1.val < e2.val ? 1 : 0;
}
ll sum[N];
int vis[N], vis1[N];
int n, k;
void dfs(int l, int r, ll s1, ll s2, int c1, int c2, int m1, int m2) {
	if (((l - 1) == r) && ((s1 - m1) > m1) && ((s2 - m2) > m2)) {
		printf("Yes\n");
		for (int i = r - 2 * k + 1; i <= r; i++) {
			if (vis1[i] == 1)
				printf("%d ", edge[i].p);
		}
		for (int i = r - 2 * k + 1; i <= r; i++) {
			if (vis1[i] == 2)
				printf("%d ", edge[i].p);
		}
		exit(0);
	}
	if (c1 != k) {
		vis1[l] = 1;
		dfs(l + 1, r, s1 + edge[l].val, s2, c1 + 1, c2, edge[l].val, m2);
	}
	if (c2 != k) {
		vis1[l] = 2;
		dfs(l + 1, r, s1, s2 + edge[l].val, c1, c2 + 1, m1, edge[l].val);
	}
}
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &edge[i].val);
		edge[i].p = i;
	}
	sort(edge + 1, edge + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + edge[i].val;
		if (i >= k && sum[i - 1] - sum[i - k] > edge[i].val)
			vis[i] = 1;
	}
	for (int i = k; i <= n; i++) {
		for (int j = i + k; j <= n; j++) {
			if (vis[i] && vis[j]) {
				printf("Yes\n");
				for (int t = i - k + 1; t <= i; t++)
					printf("%d ", edge[t].p);
				for (int t = j - k + 1; t <= j; t++)
					printf("%d ", edge[t].p);
				return 0;
			}
		}
	}
	for (int i = 2 * k; i <= n; i++) {
		dfs(i - 2 * k + 1, i, 0, 0, 0, 0, 0, 0);
	}
	printf("No\n");
	return 0;
}