Codeforces Contest 1070 problem E Getting Deals Done —— 二分

2024-04-07 00:32

本文主要是介绍Codeforces Contest 1070 problem E Getting Deals Done —— 二分,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Polycarp has a lot of work to do. Recently he has learned a new time management rule: “if a task takes five minutes or less, do it immediately”. Polycarp likes the new rule, however he is not sure that five minutes is the optimal value. He supposes that this value d should be chosen based on existing task list.

Polycarp has a list of n tasks to complete. The i-th task has difficulty pi, i.e. it requires exactly pi minutes to be done. Polycarp reads the tasks one by one from the first to the n-th. If a task difficulty is d or less, Polycarp starts the work on the task immediately. If a task difficulty is strictly greater than d, he will not do the task at all. It is not allowed to rearrange tasks in the list. Polycarp doesn’t spend any time for reading a task or skipping it.

Polycarp has t minutes in total to complete maximum number of tasks. But he does not want to work all the time. He decides to make a break after each group of m consecutive tasks he was working on. The break should take the same amount of time as it was spent in total on completion of these m tasks.

For example, if n=7, p=[3,1,4,1,5,9,2], d=3 and m=2 Polycarp works by the following schedule:

Polycarp reads the first task, its difficulty is not greater than d (p1=3≤d=3) and works for 3 minutes (i.e. the minutes 1, 2, 3);
Polycarp reads the second task, its difficulty is not greater than d (p2=1≤d=3) and works for 1 minute (i.e. the minute 4);
Polycarp notices that he has finished m=2 tasks and takes a break for 3+1=4 minutes (i.e. on the minutes 5,6,7,8);
Polycarp reads the third task, its difficulty is greater than d (p3=4>d=3) and skips it without spending any time;
Polycarp reads the fourth task, its difficulty is not greater than d (p4=1≤d=3) and works for 1 minute (i.e. the minute 9);
Polycarp reads the tasks 5 and 6, skips both of them (p5>d and p6>d);
Polycarp reads the 7-th task, its difficulty is not greater than d (p7=2≤d=3) and works for 2 minutes (i.e. the minutes 10, 11);
Polycarp notices that he has finished m=2 tasks and takes a break for 1+2=3 minutes (i.e. on the minutes 12,13,14).
Polycarp stops exactly after t minutes. If Polycarp started a task but has not finished it by that time, the task is not considered as completed. It is allowed to complete less than m tasks in the last group. Also Polycarp considers acceptable to have shorter break than needed after the last group of tasks or even not to have this break at all — his working day is over and he will have enough time to rest anyway.

Please help Polycarp to find such value d, which would allow him to complete maximum possible number of tasks in t minutes.

Input
The first line of the input contains single integer c (1≤c≤5⋅104) — number of test cases. Then description of c test cases follows. Solve test cases separately, test cases are completely independent and do not affect each other.

Each test case is described by two lines. The first of these lines contains three space-separated integers n, m and t (1≤n≤2⋅105,1≤m≤2⋅105,1≤t≤4⋅1010) — the number of tasks in Polycarp’s list, the number of tasks he can do without a break and the total amount of time Polycarp can work on tasks. The second line of the test case contains n space separated integers p1,p2,…,pn (1≤pi≤2⋅105) — difficulties of the tasks.

The sum of values n for all test cases in the input does not exceed 2⋅105.

Output
Print c lines, each line should contain answer for the corresponding test case — the maximum possible number of tasks Polycarp can complete and the integer value d (1≤d≤t) Polycarp should use in time management rule, separated by space. If there are several possible values d for a test case, output any of them.

Examples
inputCopy
4
5 2 16
5 6 1 4 7
5 3 30
5 6 1 4 7
6 4 15
12 5 15 7 20 17
1 1 50
100
outputCopy
3 5
4 7
2 10
0 25
inputCopy
3
11 1 29
6 4 3 7 5 3 4 7 3 5 3
7 1 5
1 1 1 1 1 1 1
5 2 18
2 3 3 7 5
outputCopy
4 3
3 1
4 5
Note
In the first test case of the first example n=5, m=2 and t=16. The sequence of difficulties is [5,6,1,4,7]. If Polycarp chooses d=5 then he will complete 3 tasks. Polycarp will work by the following schedule:

Polycarp reads the first task, its difficulty is not greater than d (p1=5≤d=5) and works for 5 minutes (i.e. the minutes 1,2,…,5);
Polycarp reads the second task, its difficulty is greater than d (p2=6>d=5) and skips it without spending any time;
Polycarp reads the third task, its difficulty is not greater than d (p3=1≤d=5) and works for 1 minute (i.e. the minute 6);
Polycarp notices that he has finished m=2 tasks and takes a break for 5+1=6 minutes (i.e. on the minutes 7,8,…,12);
Polycarp reads the fourth task, its difficulty is not greater than d (p4=4≤d=5) and works for 4 minutes (i.e. the minutes 13,14,15,16);
Polycarp stops work because of t=16.
In total in the first test case Polycarp will complete 3 tasks for d=5. He can’t choose other value for d to increase the number of completed tasks.

题意:

给你n道题,每道题都有一个难度,解决它需要花掉相应难度的时间,做m道题目需要休息这m题累计和的时间,但是最后一次不需要,你总共有t的时间,假设你会做难度为d的题目,那你一旦遇到一道难度不超过d的题目,你就会把它做出来,问你你最多能做多少题目,以及做的题目难度不超过多少(d有多种解,输出任意一种)

题解:

我们不能二分难度,因为它不符合二分的性质:你将难度调小,可能做出比现在少的题目,你将难度调大,也可能做出比现在少的题目,所以只能二分做的题目数量,而这个是符合二分性质的,因为做的题目越多,需要的时间肯定就越大,想到了这一点,这道题就做出来了
check中,tim表示用了多少时间,sum表示在一个m中,需要多少时间,cnt表示能做的题目的数量,由于同一难度的题目数量不止一个,那么我们就要在for的时候判断是否已经可以。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
ll a[N],b[N];
int n,m;
ll t;
bool check(int x)
{int up=b[x];ll tim=0,sum=0,cnt=0;for(int i=1;i<=n;i++){if(cnt%m==0&&cnt!=0&&cnt!=x)tim+=sum*2,sum=0;if(tim>t)return 0;if(a[i]<=up){cnt++;sum+=a[i];}if(cnt>=x&&tim+sum<=t)return 1;}if(tim+sum>t)return 0;return 1;
}
int main()
{int c;scanf("%d",&c);while(c--){scanf("%d%d%lld",&n,&m,&t);for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i];sort(b+1,b+1+n);int l=0,r=n,mid,ans;while(r>=l){mid=l+r>>1;if(check(mid))ans=mid,l=mid+1;elser=mid-1;}printf("%d %lld\n",ans,b[ans]==0?1:b[ans]);}return 0;
}

这篇关于Codeforces Contest 1070 problem E Getting Deals Done —— 二分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881232

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta

poj 3692 二分图最大独立集

题意: 幼儿园里,有G个女生和B个男生。 他们中间有女生和女生认识,男生男生认识,也有男生和女生认识的。 现在要选出一些人,使得这里面的人都认识,问最多能选多少人。 解析: 反过来建边,将不认识的男生和女生相连,然后求一个二分图的最大独立集就行了。 下图很直观: 点击打开链接 原图: 现图: 、 代码: #pragma comment(

poj 2112 网络流+二分

题意: k台挤奶机,c头牛,每台挤奶机可以挤m头牛。 现在给出每只牛到挤奶机的距离矩阵,求最小化牛的最大路程。 解析: 最大值最小化,最小值最大化,用二分来做。 先求出两点之间的最短距离。 然后二分匹配牛到挤奶机的最大路程,匹配中的判断是在这个最大路程下,是否牛的数量达到c只。 如何求牛的数量呢,用网络流来做。 从源点到牛引一条容量为1的边,然后挤奶机到汇点引一条容量为m的边