自动搬运

查看原文

来自洛谷，原作者为

	luyanlin **

搬运于2025-08-24 23:17:47，当前版本为作者最后更新于2025-07-25 18:32:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

引理

这道题目很显然是一道贪心题目，只要从耗时小的物品开始解决就可以解决尽可能多的问题。证明如下：我们可以使用反证法。假设有一个问题所用的时间，要大于我们选择去解决的问题所需要的时间，而最后可以解决的问题却比原来多，那我们一定可以选择耗时更小的问题解决，来节省更多的时间，解决更多的问题。再正推证明：顺序一定是先小后大。先设两个问题，耗时分别为 $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;
}

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

完结！

撒花！