#301 (div.2) B. School Marks
发布时间：2020-12-13 20:44:02 所属栏目：PHP教程 来源：网络整理
导读：1.题目描写：点击打开链接 2.解题思路：本题利用贪心法解决。比赛的时候看错了，把y理解成了最小，花了半天去写1个毛病的代码，最后才发现y指的是中位数。。教训很是惨重！本题可以先满足中位数y的要求，剩下的都设为1便可。给定了n，那末可知，最多只能有(n
|
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;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
推荐文章
站长推荐
热点阅读