#301 (div.2) B. School Marks
來源：程序員人生 發布時間：2015-06-16 08:49:52 閱讀次數：3164次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
