品牌做网站还是app,网站中的横幅怎么做,网站建设公司岳阳,商会网站建设开发解析
这题可以转化一下#xff1a; #xff08;《神笔马良》。。。。#xff09; 计算这些长方形对应下标的总加和 我们可以一层一层往上垒,假设第i层起始点为xi#xff0c;总和为sumi#xff0c;再设从1到i的前缀和为si 显然第一层x11#xff0c;sum1sn 对于第二层x2 《神笔马良》。。。。 计算这些长方形对应下标的总加和 我们可以一层一层往上垒,假设第i层起始点为xi总和为sumi再设从1到i的前缀和为si 显然第一层x11sum1sn 对于第二层x2sum2tot[x2,n]sn-s[x2-1] 对于第三层x3sum3sn-s[x3-1] 。。。 对于第k层xksumksn-s[xk-1] 最后累加sum即答案 显然答案整理一下应为k*sn-(s[x2-1]s[x3-1]…s[xk-1]) 要使ans最大显然要使括号内最小 那么我们只需找出最小的k-1个因为第一层不减最小的前缀和再用k*sn减去他们即可 注意因为xkn,xk-1n-1,所以sn是不能作为减数的
代码
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includeiostream
#includestring
#includequeue
#includevector
using namespace std;
int n,k;
int a[300500];
long long s[300500]{ };
bool cmp(long long x,long long y){return xy;
}
int main(){scanf(%d%d,n,k);for(int i1;in;i){scanf(%d,a[i]);s[i]s[i-1]a[i];}long long anss[n]*k;sort(s1,sn,cmp);//最后一个不能取 for(int i1;ik-1;i){ans-s[i];}printf(%lld\n,ans);return 0;
}AC快乐
