题解：P12733 磨合

Nahia · 2025-08-21 20:58:48 · 题解

思路

先考虑贪心，对其进行排序。然后对其进行前缀和，然后再使用二分来查找答案。

设排完序后的难度数组为 d，则对其做前缀和 S_n = \sum\limits_{i=1}^{n} d_i。再对解决前 i 个问题所需的时间做前缀和，即 T_n = \sum\limits_{i=1}^{n}S_i。输出时二分找到可以解决的题目个数即可。

:::info[可行性说明] 为什么可行？以样例 1 为例，排序后求前缀和 S = \{1,4,11\}，那么我们得到 T = \{1,5,16\}。以 T_2 为例，T_2 = S_2+S_1 = d_1+d_2+d_1 = 2 \times d_1+d_2，正好是第一个做第二道题，第二个做第一道题所花费的时间。为了让时间消耗最少，我们需要让小的序号去乘上难度大的题，即先做难的题。 :::

:::warning{open} 十年 OI 一场空，不开 long long 见祖宗。 :::

solution

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i = a;i<=b;i++)
using namespace std;
inline __int128 read(){__int128 x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
inline void write(__int128 x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}
ll a[1000005];
int main(){
    int n = read(),q = read();
    For(i,1,n) a[i] = read();
    sort(a+1,a+n+1);
    For(i,1,n) a[i]+=a[i-1];
    For(i,1,n) a[i]+=a[i-1];//两次前缀和
    while(q--){
        ll t = read();
        write(upper_bound(a+1,a+n+1,t)-a-1);//二分找到在t时间内最多能做多少题
        putchar('\n');
    }
    return 0;
}