CF1070E Getting Deals Done
题意翻译
题目描述
Polycarp有很多工作要做。最近他学会了一条新的时间管理技巧：“如果任务需要五分钟或更短时间，请立即执行”。Polycarp喜欢新技巧，但他不确定五分钟是最佳值。他认为这个值 d（分钟）应根据现有任务列表选择。

Polycarp有一份长度为 n 的要完成的任务清单。第 i 个任务有一个需要的时间Pi，即它确切地需要 Pi 分钟来完成。Polycarp从第一个到第 n 个逐个浏览任务。如果任务所需时间是 d 或更少，Polycarp立即开始执行任务。如果任务需要时间大于 d ，他不会去完成这个任务。列表中的任务的顺序是固定的了，所以，不容许你重新排序。当Polycarp阅读任务或跳过任务时，Polycarp不会花任何时间。

Polycarp有 T 分钟完成任务。但他不想一直工作。他决定在每做 m 个任务后休息一下。每次休息时间应该与完成这 m 个任务的时间相同。

例如，如果 N = 7，p = [3,1,4,1,5,9,2]，d = 3 和 m = 2 ，Polycarp的工作所需时间如下：

Polycarp读取第一个任务，其难度不大于 d ，并使用了 3 分钟（即分钟 1， 2 ，3 ）;

Polycarp读取第二项任务，其难度不大于 d ，并使用 1 分钟（即分钟 4 ）;

Polycarp注意到他已经完成了 m = 2 个任务并休息 3 + 1 = 4 分钟（即分钟 5,6,7,8 ）;

Polycarp读取第三项任务，其难度大于 d ，所以Polycarp不花任何时间跳过它;

Polycarp读取第四项任务，其难度不大于 d ，并适用于 1 1分钟（即分钟 9 ）;

Polycarp读取第五项和第六项任务，跳过他们两个。

Polycarp读取第七项任务，其难度不大于 d ，并使用 2 分钟（即分钟 10，11 ）;、

Polycarp注意到他又完成了 m = 2 个任务并休息 1 + 2 = 3分钟（即分钟 12,13,14 ）。

Polycarp会使用 T 分钟来完成任务。如果Polycarp启动任务但尚未完成任务，则该任务不会被视为已完成。

Polycarp认为在做完最后的任务之后可以接受比本来更短的休息时间，甚至根本没有休息——他的工作日结束了，他还有足够的时间休息。

请帮助Polycarp找到这样的价值 d ，使他能够在 T 分钟完成最多的任务。

输入输出格式
输入格式：
输入的第一行包含单个整数 C （1≤ C ≤50000）表示数据组数。

对于每组数据，有两行。

第一行包含三个以空格分隔的整数 n ，m 和 T （1 ≤ n ≤200000，1≤ m ≤200000，1≤ T ≤40000000000）

测试用例的第二行包含 n 个整数（用空格分割），Pi表示每个任务所需时间（1≤ Pi ≤200000）

PS:所有 n 的总和不超过200000
输出格式：
输出 C 行，每行应包含对应数据的答案 - Polycarp可以完成的最大任务数 N 和整数值 d 。

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

4 3
3 1
4 5

首先要注意的是要用二分法必须是排好序的数组，本题要求不能排序，那么就用数组 b [ N ] b[N] b[N]来复制一下，将数组b排序。
本题中的标准d是自己选的，所以就表明做哪些任务是自己选的，所以二分任务的件数，最小时间d就是做n件的 b [ n ] b[n] b[n],然后正常模拟题意即可，注意判断条件为能否做完mid件事以及是否超时

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ifstream in("input.txt");
ofstream out("output.txt");
#define debug(x) cout<<"# "<<x<<endl
const ll N=200010;
//const ll base=137;
//const ll mod=2147483647;
//const ll INF=1<<30;
ll n,m,C,t,d,a[N],task,b[N];
bool check(ll x,ll d)
{
    task=0;
    ll rest=0,time=0;
    for(int i=1;i<=n;++i)
    {
        if(a[i]>d)continue;//做不了
        rest+=a[i];
        task++;
        time+=a[i];
        if(task==x)
            if(time<=t)return true;//未超时returnn true
            else return false;//超时
        if(task%m==0)//每做m件事休息一下
            time+=rest,rest=0;
        if(time>t)//超时
            return false;
    }
    return false;
}
int main()
{
    scanf("%lld",&C);
    while(C--)
    {
        scanf("%lld %lld %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);
        ll l=1,r=n,ans=0;
        while(l<=r)
        {
            ll mid=(l+r)>>1;
            if(check(mid,b[mid]))
                ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%lld %lld\n",ans,ans<=0?1:b[ans]);//注意特判0的情况
    }
}

有任何疑问欢迎评论哦虽然我真的很菜