P7697 [COCI 2009/2010 #4] OGRADA题目背景Matjia 需要粉刷他的旧篱笆。题目描述篱笆是由n nn块木板做成的每块木板宽1 11厘米高度不一。为了方便快捷他给自己买了一个宽x xx厘米的超级油漆辊。然而超级油漆辊来了一个陷阱——Matija 必须始终使辊子紧密地整个接触木板否则油漆会滴到四周并污渍所有东西。此外辊子必须始终与地面平行以防泄漏。这意味着为了让 Matija 安全地使用压路机他需要选择x xx块木板并从最下面的木板的底部到顶部一次涂上油漆。然后他选择一些其他的木板油漆它们以此类推。这使得一些木板的部分没有上漆。Matija 必须用牙刷刷这些部分。这显然是相当乏味的所以他请你帮他编写一个程序求出他需要手动刷漆的最小面积。因为有不止一种方法可以做到这一点他也想知道需要使用超级油漆辊的最少次数。输入格式输入共两行。第一行两个整数n , x n,xn,x分别代表木板的个数和超级油漆辊的宽度。第二行n nn个正整数h 1 , h 2 , … , h n h_1,h_2,\dots,h_nh1​,h2​,…,hn​表示每个木板的高度。输出格式输出共两行。第一行一个整数表示 Matjia 需要手动刷漆的最小面积。第二行一个整数表示在手动刷漆的面积最小的前提下需要使用超级油漆辊的最少次数。输入输出样例 #1输入 #15 3 5 3 4 4 5输出 #13 2输入输出样例 #2输入 #210 3 3 3 3 3 3 3 3 3 3 3输出 #20 4输入输出样例 #3输入 #37 4 1 2 3 4 3 2 1输出 #34 4说明/提示【样例 1 解释】对于样例1 11Matjia 需要使用两次超级油漆辊。第一次用超级油漆辊粉刷第1 , 2 , 3 1,2,31,2,3个木板粉刷高度为3 cm 3\text{ cm}3cm因此粉刷面积为9 cm 2 9\text{ cm}^29cm2。第二次用超级油漆辊粉刷第3 , 4 , 5 3,4,53,4,5个木板粉刷高度为4 cm 4\text{ cm}4cm因此粉刷面积为12 cm 2 12\text{ cm}^212cm2。因为两次粉刷有3 cm 2 3\text{ cm}^23cm2的面积重叠因此剩下的需要手动粉刷的面积为5 3 4 4 5 − 9 − 12 3 3 cm 2 53445-9-1233\text{ cm}^253445−9−1233cm2。可以证明这样的方案需要手动粉刷的面积是最小的并且使用超级油漆辊的次数也是最少的。具体可以结合下图理解【数据范围】对于所有数据1 ⩽ n ⩽ 10 6 1\leqslant n\leqslant 10^61⩽n⩽1061 ⩽ x ⩽ 10 5 1\leqslant x\leqslant 10^51⩽x⩽1051 ⩽ h i 10 6 1\leqslant h_i10^61⩽hi​106。【题目来源】本题来源自COCI 2009-2010 CONTEST 4 T4 OGRADA按照原题数据配置满分100 100100分。由 Eason_AC 翻译整理提供。C实现#includebits/stdc.husingnamespacestd;constintN1000005;#defineintlonglongintmx[N],q[N1],a[N],x,n,brush[N],head,tail,sum;signedmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnx;for(inti1;in;i)cina[i],suma[i];intlstans0;for(inti1;in;i){while(headtaila[q[tail]]a[i])tail--;while(headtailq[head]i-x)head;q[tail]i;if(ix)mx[i-x1]a[q[head]],sum-1ll*x*a[q[head]],sum1ll*min(a[q[head]],lstans)*(x-1),lstansa[q[head]];}for(inti1;in;i){while(headtailmx[q[tail]]mx[i])tail--;while(headtailq[head]i-x)head;q[tail]i;brush[i]mx[q[head]];}intbeg-10000000,cnt0;for(inti1;in;i)if(brush[i]!brush[i-1]||ibegx)cnt,begi;coutsum\ncnt;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容