pocw.pw,luciano rivarola,错爱2吻戏
给出一个长度为\(n\)的序列\(a\),要求分为恰好\(k\)段。第\(i\)个点的贡献是\(a_i \times f(i)\),\(f(x)\)表示x所属的是第几段。
非常巧妙的一个思路。
先让每个元素都选k遍。然后不断的删除。
具体做法就是,先求一遍前缀和。然后找出前缀和最小的\(k-1\)个前缀,将其从答案中减去。初始答案为所有元素和\(\times k\)
这样被减j遍的元素就位于第\(k-j\)段中。因为是前缀和。所以前边点被减的次数一定大于等于后边。然后就符合题意了。
/* * @author: wxyww * @date: 2019-06-06 07:50:48 * @last modified time: 2019-06-06 07:56:06 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 300000 + 100; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } ll a[n]; int main() { int n = read(),k = read(); for(int i = 1;i <= n;++i) a[i] = read() + a[i - 1]; ll ans = a[n] * k; sort(a + 1,a + n); for(int i = 1;i <= k - 1;++i) ans -= a[i]; cout<<ans; return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论