題目鏈接

技能升級

個人思路

需要給n個技能添加技能點，無論技能點加成如何衰減，每次始終都是選擇當前技能加點加成最高的那一項技能，所以最后一次的加點一定也是加在當時技能攻擊加成最高的那個。此時，我們去尋找最后一次的加點的攻擊力加成的值。
詳細思路過程請看Java代碼的注釋…

參考代碼(Java/Cpp)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;public class Main {static int n;static long m;static long[][] arr;// 快速讀入對象,此處不用快讀,最后幾個數(shù)據點過不了,拿不足分數(shù)static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public static int nextInt() throws IOException {st.nextToken();return (int) st.nval;}public static long nextLong() throws IOException {st.nextToken();return (long) st.nval;}public static void main(String[] args) throws IOException {// 技能數(shù)量n = nextInt();// 加點次數(shù),根據數(shù)據范圍得為 longm = nextLong();// arr[i][0] 為第 i 個 技能初次加點的攻擊力加成// arr[i][1] 為第 i 個 技能加點的衰減數(shù)arr = new long[n][2];for(int i = 0; i < n; ++i) {arr[i][0] = nextLong();arr[i][1] = nextLong();}// 查找最后一次加點時,所增加的攻擊力,采用 左閉右閉區(qū)間int left = 0, right = 1000000; // a_i的范圍while(left <= right) {int mid = (left + right) / 2;// 如果當前情況可加點次數(shù) ≥ 限制次數(shù) m,則 增大最后一次加點數(shù)if (check(mid)) {left = mid + 1;} else {right = mid - 1;}}// cnt 計算當前已經加點的次數(shù), sum 計算當前攻擊力long cnt = 0, sum = 0;for(int i = 0; i < n; ++i) {if(arr[i][0] < right) continue;long k = (arr[i][0] - right) / arr[i][1] + 1; // 通過等差數(shù)列的形式,計算這個技能衰減能夠加點的次數(shù)cnt += k;sum += (arr[i][0] + (arr[i][0] - (k - 1) * arr[i][1])) * k / 2; // 等差數(shù)列求和}sum += (m - cnt) * right; // 可能會出現(xiàn)最后一次加點的值在多個技能里同時出現(xiàn),并且該數(shù)量超過可以加點的限制次數(shù) m,通過該方法減去多加的技能點System.out.println(sum);}static boolean check(long x) {long num = 0;for(int i = 0; i < n; ++i) {if (arr[i][0] < x) continue;num += (arr[i][0] - x) / arr[i][1] + 1; // 等差數(shù)列,求ai變成x需要經過幾次,并記上當前ai}return num >= m;}
}

Cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 3;int n;
ll m, a[N], b[N];int check(int x)
{ll cal = 0;for(int i = 0; i < n; ++i){if(a[i] < x) continue;cal += (a[i] - x) / b[i] + 1;}return cal >= m;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;for (int i = 0; i < n; ++i)cin >> a[i] >> b[i];int left = 0, right = 1e6;while(left <= right){int mid = (left + right) / 2;if(check(mid))left = mid + 1;elseright = mid - 1;}ll cnt = 0, res = 0;for(int i = 0; i < n; ++i){if(a[i] < right) continue;int k = (a[i] - right) / b[i] + 1;cnt += k;res += (a[i] * 2 - (k - 1) * b[i]) * k / 2;}res += (m - cnt) * right;cout << res;
}