CodeForces 540B School Marks (贪心)
Codeforces 贪心
2023-09-11 14:17:19 时间
题意:先给定5个数,n, k, p, x, y。分别表示 一共有 n 个成绩,并且已经给定了 k 个,每门成绩 大于0 小于等于p,成绩总和小于等于x,
但中位数大于等于y。让你找出另外的n-k个成绩。
析:利用贪心算法,首先是只能小于等于 p,也就是成绩越小越好, 然后中位数还得大于等于y,所以我们放的成绩只有两个,一个是1,另一个是y,那么是最优的,
所以每次只要判定这个就好,在判定的时候,要先排序,再找中位数,再就是每次放两个,如果n-k不是偶数,那么就放一个数,再进行。
代码如下:
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; vector<int> ans; int a[1005]; int main(){ int n, m, p, x, y, k; scanf("%d %d %d %d %d", &n, &k, &p, &x, &y); int sum = 0; for(int i = 0; i < k; ++i){ scanf("%d", &a[i]); sum += a[i]; } int ds = x - sum; int dn = n - k; bool ok = true; if(dn & 1){ sort(a, a+k); if(a[k/2] >= y){ ans.push_back(1); a[k++] = 1; ds--; } else{ ans.push_back(y); a[k++] = y; ds -= y; } dn = n - k; } for(int i = 0; i < dn; i += 2){ sort(a, a+k); int mid = a[k/2]; if(mid < y){ ans.push_back(y); ans.push_back(y); ds -= y * 2; a[k++] = y; a[k++] = y; } else { a[k++] = 1; ans.push_back(1); a[k++] = 1; sort(a, a+k); if(a[k/2] < y){ a[0] = y; ds -= y + 1; ans.push_back(y); } else{ ds -= 2; ans.push_back(1); } } } sort(a, a+k); if(a[k/2] < y || ds < 0) printf("-1"); else for(int i = 0; i < ans.size(); ++i) if(!i) printf("%d", ans[i]); else printf(" %d", ans[i]); printf("\n"); return 0; }
相关文章
- Codeforces Round #276 (Div. 2)
- codeforces 391E2 (【Codeforces Rockethon 2014】E2)
- Codeforces Round #776 (Div. 3) B. DIV + MOD
- Codeforces Round #820 (Div. 3) C Jumping on Tiles
- CodeForces 445E DZY Loves Colors
- CodeForces 732B Cormen — The Best Friend Of a Man (贪心)
- CodeForces 718A Efim and Strange Grade (贪心)
- CodeForces 711B Chris and Magic Square (暴力,水题)
- CodeForces 707B Bakery (水题,暴力,贪心)
- CodeForces 706D Vasiliy's Multiset (字典树查询+贪心)
- CodeForces 288A Polo the Penguin and Strings (水题)
- 【Codeforces 738D】Sea Battle(贪心)
- codeforces 551 C GukiZ hates Boxes
- Codeforces Round #315 (Div. 2)