C语言实现蓝桥杯算法训练Twok-ConvexPolygonsxyf0209的博客-

点击👇邮我

试题 算法训练 Two k-Convex Polygons

                                                                                  蓝桥杯试题解答汇总链接

资源限制

       时间限制：500ms 内存限制：256.0MB

问题描述

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

数据规模与约定

2k ≤ n ≤ 1000 3 ≤ k ≤ 10 1 ≤ length of each stick ≤ 10^9 

试题解析

k根棍子能组成k凸边形的条件：任何边小于其他所有边的和（即最大边小于其他所有边的和） 

证：设sum为k-1条边之和，a为最大边，x为其他边；若a为和sum的组成之一，又a>x，所以只要sum>a即可

又只要找到一种组合情况即可故我们先对样本数据从小到大排列此时可得若存在不连续组合那么它一定存在连续的组合以下拿k=3举例 

证：设x,∈[1,n],k=3
若a_x+a_x+2>a_x+4又a_x<a_x+1对任意x∈[1,n]成立则有a_x+3+a₂>a₄所以我们只需要找到连续的组合情况即可，但我们每次要找的是2k条边所以可能出现这2k条边是连续编号，但组合不是连续的情况，这种情况需要暴搜，连续的情况枚举就可以了

代码

#include<stdio.h> int n,k,v[1000],flage = 0;// n、k与题意一致；v数组用来暴搜标记一组的k根棒子；flag用来标记是否存在满足条件的2k根棍子的组合  void BubbleSort(int a[][2],int n){// 冒泡排序算法用于对给出样本的进行从小到大的排序  int f = 1,i,j,t; for(i = 0;i < n&&f == 1;i++){   f = 0; for(j = n-1;j > i;j--){ if(a[j-1][0] > a[j][0]){     f = 1;     t = a[j-1][0];     a[j-1][0] = a[j][0];     a[j][0] = t;     t = a[j-1][1];     a[j-1][1] = a[j][1];     a[j][1] = t; } } } } int sum(int a[][2],int low,int high){// 求和函数用于求下标为low-high的样本的和  int i,m = 0; for(i = low;i <= high;i++){   m += a[i][0]; } return m; } void dfs(int a[][2],int low,int high,int sum1,int sum2,int count1,int count2,int num1,int num2){// 暴搜求不连续的组合  // low、high分别为递归起点和终点；sum1、sum2分别统计各组数据的长度总和； // c1、c2分别统计各小组的已入选的数据个数；mx1、mx2分别标记每组当前数据中最后一个数据的值  int i; if(low == high+1&&flage == 0){//递归至两组都选满k个时即low=high+1且目前不存在这样的情况进入  if(sum1-num1 > num1&&sum2-num2 > num2){ printf("Yesn");       flage = 1;// 满足条件则标记flage为1表示存在这样的情况  for(i = high-2*k+1;i <= high;i++){ if(v[i] == 0){// 先输出第一组  printf("%d ",a[i][1]); } } for(i = high-2*k+1;i <= high;i++){ if(v[i] == 1){// 在输出第二组  printf("%d ",a[i][1]); } } } } if(count1 != k){// 先对第一组进行递归满k个后在递归第二组       v[low] = 0;// 第一组成员标记为0  dfs(a,low + 1,high,sum1 + a[low][0],sum2,count1 + 1,count2,a[low][0],num2); } if(count2 != k){// 第一组选好第二组递归开始       v[low] = 1;// 第二组成员标记为1  dfs(a,low + 1,high,sum1,sum2 + a[low][0],count1,count2 + 1,num1,a[low][0]); } } int main(){ scanf("%d%d",&n,&k); int i,j,a[n][2]; for(i = 0;i < n;i++){ scanf("%d",&a[i][0]);   a[i][1] = i+1;// 给每根棍子标号  } BubbleSort(a,n);// 从小到大排序  for(i = 0;i <= n-2*k;i++){ // 组合为连续的情况  if(sum(a,i,i+k-2) > a[i+k-1][0]&&sum(a,i+k,i+2*k-2) > a[i+2*k-1][0]){ printf("Yesn"); for(j = i;j < i+2*k;j++){ printf("%d ",a[j][1]); } return 0; }// 组合为不连续的情况  else if(sum(a,i+k,i+2*k-2) > a[i+2*k-1][0]){ dfs(a,i,i+2*k-1,0,0,0,0,0,0);// 暴搜  if(flage){// 有一种情况满足直接退出程序  return 0; } } } printf("No");// 没有满足的输出No  return 0; }