#301 (div.2) B. School Marks
来源：程序员人生 发布时间：2015-06-16 08:49:52 阅读次数：3005次
1.题目描写：点击打开链接
2.解题思路：本题利用贪心法解决。比赛的时候看错了，把y理解成了最小值，花了半天去写1个毛病的代码，最后才发现y指的是中位数。。教训很是惨重！本题可以先满足中位数y的要求，剩下的都设为1便可。给定了n，那末可知，最多只能有(n⑴)/2个数要小于中位数y。因此可以事前统计1下输入的数中有xc1个是小于y的，同时累加和sum。如果sum>x或c1>(n⑴)/2，则无解。否则，最少还要添加max(0,(n+1)/2-(k-c1))个中位数。添加终了以后，由于sum不能超过x，因此只用将剩下的所有数设为1便可。如果终究sum>x，那末无解，否则输出解。
3.代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;
#define N 1000+5
int n, k, p, x, y;
vector<int>a;
int main()
{
//freopen("t.txt", "r", stdin);
while (~scanf("%d%d%d%d%d", &n, &k, &p, &x, &y))
{
int sum = 0;
a.clear();
int c1 = 0;
for (int i = 0; i < k; i++)
{
int sx;
scanf("%d", &sx);
if (sx < y)c1++;
sum += sx;
}
if (sum>x || c1>(n - 1) / 2)puts("⑴");//c1不能超过最大限制(n⑴)/2
else{
int m = max(0, (n + 1) / 2 - k + c1);//还需要添加的中位数是0和(n+1)-(k-c1)中的较大者
for (int i = 0; i < m; i++)
a.push_back(y);
sum += m*y;
if (sum + n - k - m>x)puts("⑴");
else{
for (int i = 0; i < n - k - m; i++)
a.push_back(1);
int len = a.size();
for (int i = 0; i < len; i++)
printf("%d%c", a[i], i == len - 1 ? '
' : ' ');
}
}
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
