AcWing 277. 饼干(Java)
原题链接
中等
作者:
上杉
,
2021-06-14 19:30:44
,
所有人可见
,
阅读 307
import java.util.Arrays;
import java.util.Scanner;
/**
* @program: 算法题
* @author: 上杉
* @create: 2021-06-14 18:05
**/
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int N = input.nextInt();
int M = input.nextInt();
Child[] children = new Child[N + 1];
for (int i = 1; i <= N; i++) {
children[i] = new Child(input.nextInt(),i);
}
Arrays.sort(children,1,N+1);
int[] sum = new int[N + 1];//排完序之后前i个孩子的贪婪度的前缀和,方便快速计算答案
for (int i = 1; i <= N; i++) {
sum[i] = sum[i-1] + children[i].g;
}
int[][] dp = new int[N+1][M+1];//dp[i][j]代表前i个孩子分了j块饼干怨气的最小值
for (int i = 0; i <= N; i++) {
Arrays.fill(dp[i],0x3f3f3f3f);
}
dp[0][0] = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (j < i)continue;//每个孩子必须分配一个饼干
//集合划分:dp[i][j]以最后分配了几个1进行划分
dp[i][j] = dp[i][j-i];//没有分配1,所有孩子同时减少一个饼干
for (int k = 1; k <= i; k++) {
//分配了1-i个1,这里可能会存在所有孩子分配1之后,饼干数量和j不符合的情况,
// 但是我们初始化了INF,所以非法情况不会取到
dp[i][j] = Math.min(dp[i][j],dp[i-k][j-k]+(sum[i] - sum[i-k]) *(i - k));
}
}
}
System.out.println(dp[N][M]);
int[] ans = new int[N+1];
int i = N;
int j = M;
int t = 0;//记录每个孩子都需要加上的饼干数量
while (i > 0){
if (dp[i][j] == dp[i][j-i]){
j -= i;
t++;
}else {
for (int k = 1; k <= i; k++) {
if (dp[i][j] == dp[i-k][j-k]+(sum[i] - sum[i-k]) *(i - k)){
//最后有k个1
for (int l = i - k + 1; l <= i; l++) {
ans[children[l].index] = 1 + t;
}
i -= k;
j -= k;
}
}
}
}
for (int k = 1; k <= N; k++) {
System.out.print(ans[k] + " ");
}
}
static class Child implements Comparable<Child>{
int g;
int index;
public Child(int g, int index) {
this.g = g;
this.index = index;
}
@Override
public int compareTo(Child o) {
return o.g - this.g;
}
}
}