codeforce 1070 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.InputThe 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.OutputPrint 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

Input

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

Output

3 5

4 7
2 10
0 25
题意：有n个任务，每一个任务都有一个难度pi你有t个时间去完成这些任务，对于难度为pi的任务你需要pi个时间去完成,对于你要完成的任务有一个限制范围d(你只能完成难度小于等于d的任务）,当你每完成m个任务时你需要休息;
一旦遇到难度比d小的任务你必须完成它;
题解：这道题的关键是找到d的最小下界，如果找到d这道题也就解决了，而这个题就转换成了二分找最大化最小值的问题;再不休息的情况下二分查找mid，找到符合条件的最小值就可以啦（符合条件：难度小于d的任务难度之和必须大于t)
这样我们就找到了d(由于mid,和mid-1不确定，所以我们要都搜索一下），输出任务的最大值，和d就可以啦；这道题由于数据量比较大，所以cin会超时，所以要用scanf;

 #include<cstdio>

 #include<cstring>

 #include<stack>

 #include<queue>

 #include<algorithm>

 #include<iostream>

 #include<map>

 #include<vector>

 #define PI acos(-1.0)

 using namespace std;

 typedef long long ll;

 ll m,n,k,kmp,ans1,ans2=,flag;

 map<ll,pair<ll,ll> >mp;

 vector<ll>str;

 bool check(ll mid)

 {

     ll  sum=,num=,cnt=,kk=,kmp;

     for(ll i=; i<m; i++)

     {

         if(str[i]<=mid)

         {

             if(num==n)

             {

                 num=;

                 kk+=sum*;

                 sum=;

             }

             num++;

             sum+=str[i];

             cnt++;

             if(sum+kk<=k)

             {

                 ans1=cnt;

                 ans2=mid;

                 flag=;

             }

         }

     }

     if(flag)//如果满足条件就存起来

     {

         mp[mid].first=ans1;

         mp[mid].second=ans2;

     }

     return kk+sum>k;

 }

 void solve()

 {

     cin>>m>>n>>k;

     ll p;

     str.clear();

     for(ll i=; i<m; i++)

     {

         scanf("%lld",&p);

         str.push_back(p);

     }

     ll pos=k;

     for(ll l=,r=k; l<=r;)

     {

         ll mid=(l+r)/;

         if(check(mid))

         {

             r=mid-;

             pos=mid;

         }

         else

         {

             l=mid+;

         }

     }

     check(pos-);

     if(!flag)

         cout<<ans1<<" "<<""<<endl;

     else//找到可行解

     {

         if(mp[pos].first>mp[pos-].first)//我用了pair，只是秀一下操作，直接用map就可以啦

             cout<<mp[pos].first<<" "<<mp[pos].second<<endl;

           else

            cout<<mp[pos-].first<<" "<<mp[pos-].second<<endl;

     }

 }

 int main()

 {

     ll T;

     scanf("%lld\n",&T);

     while(T--)

     {

         solve();

         mp.clear();

         ans1=,ans2=;flag=;//一定要初始化

     }

 }

巴特西

codeforce 1070 E Getting Deals Done(二分求最大化最小值）

最新文章

热门文章