AcWing 3664. 数组补全
原题链接
中等
作者:
小明_3
,
2021-08-30 13:32:22
,
所有人可见
,
阅读 199
题目描述
- 数组补全
这道题我们是从中位数下手的
因为要求我们的中位数的值不小于y 所以对于中位数的左边和右边都存在n/2个数 我们在输入前k个数的时候记录大于等于中位数y的个数cnt
首先就要判断时候将剩下的所有数补到右边是否够
如果cnt+n-k<n/2+1那么就输出-1
如果够 那么我们就开始给我们的数字补数 先将我们的中位数的右边去补 右边补y 左边补1 因为我们需要满足所有的元素的之和不大于x
右边补完后 开始补左边 最后看总和是否是小于等于x如果成立就输出补全的数组 如果不成立就输出-1
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1010;
int a[N];
int n, k, p, x, y;
int main()
{
cin>>n>>k>>p>>x>>y;
int cnt =0;int sum=0;
for(int i=1;i<=k;i++)
{
cin>>a[i];
sum+=a[i];
if(a[i]>=y) cnt++;
}
if(cnt+n-k<n/2+1)
{
puts("-1");
return 0;
}
else
{
int j=k+1;
while(cnt<n/2+1) a[++k]=y,cnt++,sum+=y;
while(n-k>0) a[++k]=1,sum++;
if(sum>x) puts("-1");
else
{
for(int i=j;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
}
return 0;
}