An array bb is called to be a subarray of aa if it forms a continuous subsequence of aa , that is, if it is equal to alal , al+1al+1 , …… , arar for some l,rl,r .
Suppose mm is some known constant. For any array, having mm or more elements, let‘s define it‘s beauty as the sum of mm largest elements of that array. For example:
You are given an array a1,a2,…,ana1,a2,…,an , the value of the said constant mm and an integer kk . Your need to split the array aa into exactly kk subarrays such that:
The first line contains three integers nn , mm and kk (2≤n≤2?1052≤n≤2?105 , 1≤m1≤m , 2≤k2≤k , m?k≤nm?k≤n ) — the number of elements in aa , the constant mm in the definition of beauty and the number of subarrays to split to.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (?109≤ai≤109?109≤ai≤109 ).
In the first line, print the maximum possible sum of the beauties of the subarrays in the optimal partition.
In the second line, print k?1k?1 integers p1,p2,…,pk?1p1,p2,…,pk?1 (1≤p1<p2<…<pk?1<n1≤p1<p2<…<pk?1<n ) representing the partition of the array, in which:
If there are several optimal partitions, print any of them.
9 2 3 5 2 5 2 4 1 1 3 2
21 3 5
6 1 4 4 1 3 2 2 3
12 1 3 5
2 1 2 -1000000000 1000000000
0 1
In the first example, one of the optimal partitions is [5,2,5][5,2,5] , [2,4][2,4] , [1,1,3,2][1,1,3,2] .
The sum of their beauties is 10+6+5=2110+6+5=21 .
In the second example, one optimal partition is [4][4] , [1,3][1,3] , [2,2][2,2] , [3][3] .
大意：
这个题目是给你n个数据，让你分成k段，每一段至少m个数，并且把每一段的前m大的数求和
输出求和的结果，和分段的位置、
思路：
是求这每一段的前m大的数，其实可以转化成，求这一组数前m*k大的数之和。
至于求分段的位置，这个就有点麻烦了，可以把每一个位置初始标记为0，
然后在求sum的同时，将求过的数位置标记成1，之后求分段位置的时候，
就可以进行累加，一旦累加之和为m，说明这m个数组成了一段，也就是在这个位置将数组分段。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
struct node
{
int x,id;
}a[maxn];
bool vis[maxn];
bool cmp(node a,node b)
{
return a.x>b.x;
}
int main()
{
int n,m,k;
memset(vis,0,sizeof(vis));
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].x);
a[i].id=i;
}
sort(a+1,a+1+n,cmp);
ll sum=0;
for(int i=1;i<=m*k;i++)
{
sum+=a[i].x;
vis[a[i].id]=1;
//printf("a.id=%d\n",a[i])
}
printf("%I64d\n",sum);
int s=0;;
for(int i=1;i<=n;i++)
{
s=s+vis[i];
// printf("%d %d\n",i,s);
if(s==m&&k!=1)
{
k--;
s=0;
printf("%d ",i);
}
}
printf("\n");
return 0;
}
B. Yet Another Array Partitioning Task ——cf
原文：https://www.cnblogs.com/EchoZQN/p/10361960.html