刚看别人题解看懵了,后来测试了一下他的ac不了…
后来参考了一下其他大佬,总结出如下思路
贪心
分析题目可知,在中位数 y 前插入 1 ,在中位数 y 后插入中位数 y ,即可使所得的最终总和 s 最小
因此可先将中位数 y 插入顺序数组,求得第一个 y 的位置 m ,然后在此位置前后分别插入 l 个 1 和 r 个 y
从而使该位置 m 等于 n / 2 + 1 ,实际计算时只需求出 l 和 r
使 s 加上插入数的和,再把 x 和 s 的值进行比较,若 s 大于 x ,输出 -1 ,否则输出补充的数
在做题的时候要注意 m 记录的是哪类数的总数,以是否小于 y 进行分类讨论
以下的 m 记录小于 y 的值(写起来比较方便)
C++ 代码
#include<iostream>
using namespace std;
int main()
{
int n, k, p, x ,y;
cin >> n >> k >> p >> x >> y;
int s = 0, m = 0;
for(int i = 0; i < k; i++)
{
int a;
cin >> a;
if(a < y) m++;//m记录小于等于y的数
s += a;
}
int l = n / 2 - m;//需要补充1的数量
int r = n - k - l;//需要补充y的数量
if(r < 0) l += r, r = 0;//可能出现所给数组元素值均小于y的情况导致r的值为负数
if(s + l + r * y > x) cout << -1;
else
{
for(int i = 0; i < l; i++) cout << 1 << " ";
for(int i = 0; i < r; i++) cout << y << " ";
}
return 0;
}