题目链接

题意

给出一个长度为(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; }