当前位置: 代码迷 >> 综合 >> 蓝桥杯算法训练 ------ Two k-Convex Polygons
  详细解决方案

蓝桥杯算法训练 ------ Two k-Convex Polygons

热度:49   发布时间:2024-02-24 16:42:44.0

题目

给定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;
}