题解：AtCoder AT_awc0034_c Watering the Flower Bed

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Watering the Flower Bed【题目描述】Takahashi managesN NNflower beds arranged in a row in his garden. The flower beds are numbered1 , 2 , … , N 1, 2, \ldots, N1,2,…,Nfrom left to right, and the current moisture level of the soil in flower bedi ii(1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N) isA i A_iAi​.高桥在他的花园中管理着一排N NN个花坛。花坛从左到右编号为1 , 2 , … , N 1, 2, \ldots, N1,2,…,N花坛i ii1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N土壤当前的湿度水平为A i A_iAi​。Since he will have guests tomorrow, Takahashi wants to make all flower beds have a moisture level of at least the target valueT TTso that the flowers bloom beautifully. It is fine if the moisture level exceedsT TT.由于明天将有客人来访高桥希望所有花坛的湿度水平至少达到目标值T TT以便花朵美丽绽放。湿度水平超过T TT也可以。Takahashi can perform the following operation any number of times (possibly0 00times):高桥可以执行任意次包括0 00次以下操作Operation:Choose an integerl llsatisfying1 ≤ l ≤ N − K 1 1 \leq l \leq N - K 11≤l≤N−K1, and water theK KKconsecutive flower beds from flower bedl llto flower bedl K − 1 l K - 1lK−1using a sprinkler. This increases the moisture level of each of thoseK KKflower beds by1 11. Each operation costsC CCyen in water charges.操作选择一个满足1 ≤ l ≤ N − K 1 1 \leq l \leq N - K 11≤l≤N−K1的整数l ll并使用洒水器为从花坛l ll到花坛l K − 1 l K - 1lK−1的K KK个连续花坛浇水。这会将这K KK个花坛的湿度水平各提高1 11。每次操作的水费为C CC日元。The value ofl llchosen in each operation is arbitrary, and the same value ofl llmay be chosen in different operations.每次操作所选的l ll值可以任意且在不同操作中可以选择相同的l ll值。Find the minimum total water cost (in yen) required to make the moisture level of all flower beds at leastT TT.求使所有花坛的湿度水平至少达到T TT所需的最小总水费以日元计。【输入】N NNK KKT TTC CCA 1 A_1A1​A 2 A_2A2​⋯ \cdots⋯A N A_NAN​The first line contains the number of flower bedsN NN, the number of flower beds watered simultaneously by the sprinklerK KK, the target moisture levelT TT, and the water cost per operationC CC(yen), separated by spaces.The second line contains the initial moisture levels of each flower bedA 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1​,A2​,…,AN​, separated by spaces.【输出】Print the minimum total water cost (in yen) required to make the moisture level of all flower beds at leastT TT, as an integer on a single line.【输入样例】5 3 10 100 8 7 9 12 11【输出样例】300【算法标签】#差分#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN200005;intn,k,t,c,ans;// n: 数组长度, k: 影响范围, t: 目标值, c: 单位代价, ans: 操作次数inta[N],imos[N],cur;// a: 原始数组, imos: 差分数组, cur: 当前累计增加值signedmain(){cinnktc;// 输入参数for(inti1;in;i){cina[i];// 输入原始数组}for(inti1;in;i)// 遍历每个位置{curimos[i];// 更新当前位置的累计增加值if(a[i]curt)// 如果当前值小于目标值{intneedt-(a[i]cur);// 计算需要增加的值ansneed;// 累计操作次数if(ikn)// 如果影响范围未超出数组{imos[ik]-need;// 在差分数组记录减少}curneed;// 当前累计值增加}}coutans*cendl;// 输出总代价return0;}【运行结果】5 3 10 100 8 7 9 12 11 300