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