题解：AtCoder AT_awc0063_c Maximizing Investment

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Maximizing Investment【题目描述】Takahashi is investing inN NNstocks. The current asset value of stocki ii(1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N) isS i S_iSi​.高桥正在投资N NN只股票。股票i ii1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N的当前资产价值为S i S_iSi​。Takahashi will now perform the following operation exactlyK KKtimes.高桥现在将恰好执行K KK次以下操作。Choose one of theN NNstocks and double its current asset value.从N NN只股票中选择一只并将其当前资产价值翻倍。He may freely choose which stock to select for each operation, and the same stock may be chosen multiple times. If the same stock is chosen multiple times, the doubling operation is applied cumulatively each time. For example, if a stock with asset valueS SSis chosen3 33times, its asset value becomes2 3 × S 8 S 2^3 \times S 8S23×S8S.他每次操作可以自由选择哪只股票同一只股票可以被选择多次。如果同一只股票被选择多次每次都会应用翻倍操作累积计算。例如如果一只资产价值为S SS的股票被选中3 33次其资产价值变为2 3 × S 8 S 2^3 \times S 8S23×S8S。Takahashi wants to maximize the total asset value of allN NNstocks after performing allK KKoperations.高桥希望在执行完所有K KK次操作后最大化所有N NN只股票的总资产价值。When the choice of stocks for the operations is made optimally, find the maximum possible total asset value of theN NNstocks afterK KKoperations. Since the answer can be very large, output the maximum total modulo10 9 7 10^9 71097.当操作中选择的股票最优时求K KK次操作后N NN只股票可能的最大总资产价值。由于答案可能非常大输出对10 9 7 10^9 71097取模的最大总和。【输入】N NNK KKS 1 S_1S1​S 2 S_2S2​… \ldots…S N S_NSN​The first line contains an integerN NNrepresenting the number of stocks and an integerK KKrepresenting the number of operations, separated by a space.The second line contains integersS 1 , S 2 , … , S N S_1, S_2, \ldots, S_NS1​,S2​,…,SN​representing the asset values of each stock before the operations, separated by spaces.【输出】Output in one line the maximum total asset value of theN NNstocks when theK KKoperations are performed optimally, modulo10 9 7 10^9 71097.【输入样例】3 2 1 3 2【输出样例】15【算法标签】#快速幂#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 定义int为long long类型constintN200005,p1e97;// 常量定义intn,k,maxn-1;// n: 数组长度, k: 操作次数, maxn: 最大值ints[N],sum;// s: 数组(未实际使用), sum: 除最大值外的和// 快速幂计算 a^b mod pintqmi(inta,intb){intmul1;// 结果初始化为1while(b)// 当b不为0{if(b1)// 如果b的二进制最后一位是1{mulmul*a%p;// 累乘当前a}aa*a%p;// a自乘b/2;// b右移一位等价于b 1}returnmul;// 返回结果}signedmain(){cinnk;// 输入数组长度n和操作次数kfor(inti1;in;i){intx;cinx;// 输入数组元素maxnmax(maxn,x);// 更新最大值sumx;// 累加所有元素的和}sum-maxn;// 减去最大值得到除最大值外的和// 计算结果sum 2^k * maxncout(sumqmi(2,k)*maxn)%pendl;return0;// 程序正常结束}【运行结果】3 2 1 3 2 15