题目 https://codeforces.com/contest/1282
传送门
A Temporarily unavailable standard input/output 1 s, 256 MB
给一个线段 ab, 问除去 c 点圆心半径 r 覆盖的 线段多长, 如果圆在线段外 直接输出 ab 长度就行, 若在线段内 则输出 cout <<max(b-a-max((min(c+r,b)-max(a,c-r)),0), 0) , 迷糊的话纸上画下大概就能明白.
- B1 K for the Price of One (Easy Version) ,B2 K for the Price of One (Hard Version) standard input/output 2 s, 256 MB
- B1 k = 2, B2 k <= n, n <= 2e5 ai<=2e9
You must buy **exactly** k gifts to use the offer. 可以推出贪心求得值为最优解,
for i 0~n
当 i>=k 时, 可以直接付 a[i] 的钱买下 i-k ~ i 号货物,
当 i <k-1 且 i> 0 , 不足 k 所以不能享受折扣 需要付 a[0]+....+a[i] 的钱才能买下 0 ~ i 号货物, 所以需要求个前缀和, 至于为什么边界是 k-1 是因为数组下标 0 和 1 的故事
C Petya and Exam standard input/output 2 s, 256 MB
额, 想到了贪心, 但是没贪对, 首先给你多组数据, 每组数据给你 n t a b, 问最多能解决的问题, 其中每道题分为难易 且 有变成 mandatory(必须要解决 ddl) 的时间, 所以可以先用个 pair 存储下每道题的难易 和 时间, 再根据每道题的 ddl 从小到大 排个序, 然后可以证明当 ti-1 时间走 是最优的 (因为如果再晚的话 就要面对第 i 道题, 更早的话 没有必要) 而 ti-1 时间可以 必须把第 i 道题目之前的所有题目做完 (因为都到了 ddl) 然后把剩下的时间贪心地先做剩下题目中的简单题 时间有多余的话再做剩下题目中的难题, 然后对每个题目 取 之前已经到 ddl 的题目数和贪心数 的最大值, 有个小细节是需要在数组最后面加一个 t+1,0 因为最迟离开时间是 t , 代码如下
- #include<bits/stdc++.h>//Codeforces Round #608 (Div. 2)
- using namespace std;
- #define _for(i,a,b) for(int i = (a); i <(b); i++)
- #define _rep(i,a,b) for(int i = (a); i <= (b); i++)
- #define _per(i,a,b) for(int i = (a); i> (b); i--)
- #define ll long long
- void taskA(){
- int t;
- cin>> t;
- while(t--) {
- int a,b,c,r; cin>> a>> b>> c>> r;
- if(a> b) swap(a, b);
- if(c-r>= b || c+r <= a) cout <<b-a << '\n';
- else//(c <= b)
- cout << max(b-a-max((min(c+r,b)-max(a,c-r)),0), 0) << '\n';
- //else if(c-r <= b) cout << max(a-b-(min(c+r,b)-max(a,c-r)), 0) << '\n';
- // cout <<
- }
- return;
- }
- void taskB(){
- int t; cin>> t;
- while(t--) {
- int n,p,k; cin>> n>> p>> k;
- vector<int> a(n, 0);
- _for(i,0,n) cin>> a[i];
- int ans = 0;
- sort(a.begin(), a.end());
- _for(i,0,n) {
- if(i>= k) a[i] += a[i-k];
- //else if(i && i != k-1) a[i] += a[i-1];
- else if(i <k-1 && i) a[i] += a[i-1];
- if(a[i] <= p) ans = i+1;
- //cout << "i =" << i;
- //cout << "\tans =" << ans << "a[i]=" << a[i] << "\n";
- }cout << ans << "\n";
- }return;
- }
- void taskC(){
- int t1; cin>> t1;
- while(t1--){
- ll n,t,a,b; cin>> n>> t>> a>> b;
- vector<pair<ll, ll>> dif(n);
- ll ans = 0, cnta = 0, cntb = 0;
- _for(i,0,n) {
- cin>> dif[i].second;
- dif[i].second ? cntb++ : cnta++;
- }
- _for(i,0,n) cin>> dif[i].first;
- dif.push_back({t+1, 0});// t 时间 离去
- sort(dif.begin(), dif.end());
- ll cnt1 = 0, cnt2 = 0;
- _rep(i,0,n) {
- ll need = a*cnt1+cnt2*b;
- ll has = dif[i].first-1-need;
- if(has>= 0) {
- ll cana = min(cnta-cnt1, has/a);
- has -= a*cana;
- ll canb = min(cntb-cnt2, has/b);
- ans = max(ans, cnt1+cnt2+cana+canb);
- }
- int l = i;
- while(l < dif.size() && dif[i].first == dif[l].first) {
- if(dif[l].second) cnt2++;// 记录同一个 ddl 有几个任务, 这些都需要完成
- else cnt1++;
- l++;
- }
- i = l - 1;
- } cout << ans << '\n';
- } return;
- }
- int main(){
- iOS::sync_with_stdio(false), cin.tie(nullptr);
- //taskA();
- //taskB();
- //taskC();
- return 0;
- }
- taskB();
来源: http://www.bubuko.com/infodetail-3354884.html