題目鏈接

技能升級(jí)

個(gè)人思路

需要給n個(gè)技能添加技能點(diǎn)，無(wú)論技能點(diǎn)加成如何衰減，每次始終都是選擇當(dāng)前技能加點(diǎn)加成最高的那一項(xiàng)技能，所以最后一次的加點(diǎn)一定也是加在當(dāng)時(shí)技能攻擊加成最高的那個(gè)。此時(shí)，我們?nèi)ふ易詈笠淮蔚募狱c(diǎn)的攻擊力加成的值。
詳細(xì)思路過(guò)程請(qǐng)看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;// 快速讀入對(duì)象,此處不用快讀,最后幾個(gè)數(shù)據(jù)點(diǎn)過(guò)不了,拿不足分?jǐn)?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();// 加點(diǎn)次數(shù),根據(jù)數(shù)據(jù)范圍得為 longm = nextLong();// arr[i][0] 為第 i 個(gè) 技能初次加點(diǎn)的攻擊力加成// arr[i][1] 為第 i 個(gè) 技能加點(diǎn)的衰減數(shù)arr = new long[n][2];for(int i = 0; i < n; ++i) {arr[i][0] = nextLong();arr[i][1] = nextLong();}// 查找最后一次加點(diǎn)時(shí),所增加的攻擊力,采用 左閉右閉區(qū)間int left = 0, right = 1000000; // a_i的范圍while(left <= right) {int mid = (left + right) / 2;// 如果當(dāng)前情況可加點(diǎn)次數(shù) ≥ 限制次數(shù) m,則 增大最后一次加點(diǎn)數(shù)if (check(mid)) {left = mid + 1;} else {right = mid - 1;}}// cnt 計(jì)算當(dāng)前已經(jīng)加點(diǎn)的次數(shù), sum 計(jì)算當(dāng)前攻擊力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; // 通過(guò)等差數(shù)列的形式,計(jì)算這個(gè)技能衰減能夠加點(diǎn)的次數(shù)cnt += k;sum += (arr[i][0] + (arr[i][0] - (k - 1) * arr[i][1])) * k / 2; // 等差數(shù)列求和}sum += (m - cnt) * right; // 可能會(huì)出現(xiàn)最后一次加點(diǎn)的值在多個(gè)技能里同時(shí)出現(xiàn),并且該數(shù)量超過(guò)可以加點(diǎn)的限制次數(shù) m,通過(guò)該方法減去多加的技能點(diǎn)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需要經(jīng)過(guò)幾次,并記上當(dāng)前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;
}