1 条题解

  • 0
    @ 2022-11-19 20:24:04

    对于每次询问,只要让增加的学习量 dd 满足

    d+L+1ti×vd+L+1 \ge t_{i}\times v

    同时要让使用的魔法次数最少,考虑贪心,优先释放增加量大的魔法。可以将所有魔法根据增加量降序排序后进行前缀和,即可得到释放 ii 个魔法最多能让队友要学的知识增加 sumisum_{i}

    对于每次询问,只要二分找到满足 sumi+L+1t×vsum_{i}+L+1\ge t\times v 的最小下标 ii 即为答案,总体时间复杂度 O(nlogn)

    #include<iostream>
    #include<algorithm>
    #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    using namespace std;
    using ll = long long;
    const int N = 2e5 + 10;
    #define int ll
    
    int a[N];
    bool cmp(int a, int b) {
    	return a > b;
    }
    
    signed main() {
    	IOS
    	int n, L, v;
    	cin >> n >> L >> v;
    	for (int i = 1;i <= n;i++) {
    		cin >> a[i];
    	}
    	sort(a + 1, a + n + 1, cmp);
    	for (int i = 1;i <= n;i++) {
    		a[i] += a[i - 1];
    	}
    	int mx = a[n];  //最多可以增加的知识
    	int q;
    	cin >> q;
    	while (q--) {
    		int t;
    		cin >> t;
    		int d = t * v - L + 1; //至少应该增加的知识
    		if (d > mx) {
    			cout << -1 << endl;
    			continue;
    		}
    		int ans = lower_bound(a, a + n + 1, d) - a;//注意从a[0]找起
    		cout << ans << endl;
    	}
    	
    	return 0;
    }
    

    信息

    ID
    77
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    1
    已通过
    1
    上传者