题解：P12733 磨合

· · 题解

引理

这道题目很显然是一道贪心题目，只要从耗时小的物品开始解决就可以解决尽可能多的问题。证明如下：我们可以使用反证法。假设有一个问题所用的时间，要大于我们选择去解决的问题所需要的时间，而最后可以解决的问题却比原来多，那我们一定可以选择耗时更小的问题解决，来节省更多的时间，解决更多的问题。再正推证明：顺序一定是先小后大。先设两个问题，耗时分别为 x 和 y，顺序分别是第 i 个和第 j 个，其中 x\le y，i<j。若先解决耗时 x 的问题，则耗时为 x\times i+y\times j；若先解决耗时 y 的问题，则耗时为 y\times i+x\times j，现在就是要比较 x\times i+y\times j 和 y\times i+x\times j 的大小，先移项，得到 x\times i-y\times i 和 x\times j-y\times j，两边同除 x-y，得到 i 和 j。又因为 i<j，所以 x\times i+y\times j<y\times i+x\times j 所以一定是先小后大，这样才能使耗时最小。

算法一

排序完成了。根据引理，既然已经知道是贪心了，那么就可以对于每次询问，枚举可以选择多少可以解决的问题，时间复杂度 O(nq)。得分 54pts。

算法二

这道题目并不需要什么数据结构优化，只需要一个二分就可以解决问题了。根据引理，算法一就是在找到一个问题个数后，再让耗时最大的问题耗时尽可能小，那么我们就想到了二分。

预处理

首先预处理出选用 i 个问题所需要用的最少时间 sum_i，再使用一次引理得出只要解决耗时前 i 的问题再计算时间就可以了。

代码：

sort(a+1,a+n+1);
int sum=0;
for (int i=1;i<=n;i++){
    ans[i]=ans[i-1]+(long long)sum+(long long)a[i];
    sum+=a[i];
}

处理询问

对于每个输入的时间 t，我们可以二分用这些时间最多可以处理多少问题。由预处理的方式可以得出一个显而易见的结论：ans 数组是单调递增的。所以二分就十分可行了，我们二分可以处理的问题数 mid，然后只要判断所需要的最小时间 ans_{mid} 是不是小于等于 t 就可以了。

秀一下代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
long long ans[1000005];
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    int sum=0;
    for (int i=1;i<=n;i++){
        ans[i]=ans[i-1]+(long long)sum+(long long)a[i];
        sum+=a[i];
    }
    while (m--){
        long long t;
        scanf("%lld",&t);
        int l=1,r=n;
        int lst=0;
        while (l<=r){
            int mid=(l+r)/2;
            if (ans[mid]<=t){
                l=mid+1;
                lst=mid;
            }
            else{
                r=mid-1;
            }
        }
        printf("%d\n",lst);
    }
    return 0;
}

我觉得已经很详细了，如果有什么问题请直接炮轰我，谢谢。

完结！

撒花！