攀比
题目描述
小明在数学课上与同学无缘无故起了攀比心！老师们在教大家计数，每个同学有一排n个木棍，每个木棍上初始插着一些算珠，木棍从左到右依次编号为 1,2,3,...,n，其上的算珠数量也分别为 a1, a2, ..., an。小明认为，将这些算珠数是可以看作一个非负整数数组[a1, a2, a3, ..., an], 其字典序越小就越厉害。
小明可以将他的一些管珠那一下位置，即从一根木棍上取一颗算珠下来然后放到另一根木棍上（一次操作只能移动一颗算珠) 。小明想比其他人都厉害，但是他也不想太过分，他想知道如果他能进行最多 k 次移动操作，能得到的最小字典序的数组是怎样的。
注意，你不能从算珠数为0 的木棍上再取走一个算珠使得数显变成-1。每个木棍上可以插无限多个算珠。
数组x的字典序小于数组y当且仅当存在一个下标i，使得xi，且对于1 <= j < i存在xj = yj。例如:
[1,2,3]
输入描述
第一行2个整数n和k，表示木棍数量和小明能最多进行的移动操作次数
第二行n个整数a1, a2, ..., an，表示初始时木棍上的算珠数量。
1
输出描述
输出一行n个整数表示移动最多k次后最小字典序数组。
示例
输入
4 2
1 2 2 4
输出
0 1 2 6
解题思路
直接把k次都加到最后一个元素即可，将前面的元素尽可能地减直到k次用完。
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int []a = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
int tk = k;
for (int i = 1; i <= n - 1; i++) {
if (a[i] <= k) {
k -= a[i];
a[i] = 0;
}else {
a[i] -= k;
break;
}
}
a[n] += tk;
for (int i = 1; i <= n; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
巧克力
题目描述
小丽明天要出去和同学春游。她准备带上总面积恰好为n的巧克力板(简化起见将巧克力板视为平面图形，忽略它的厚度,只考虑面积)去和同学们一起分享。
出于美感的考虑,小丽希望她带上的巧克力板都是边长为整数的正方形;另一方面出于便携性考虑，小丽希望这些巧克力板的周长之和尽可能小,请你帮小丽找出可能的最小周长！
换句话说,小丽需要你帮忙找出k个小正方形巧克力板，边长分别为a1, a2, ..., ak,使得其面积之和,即
,恰好为要求的总面积为n；同时，使得总周长,即最小
输入描述
一行，1个整数n，表示小丽希望带上的巧克力板总面积
1 <= n <= 50000
输出描述
输出一行一个整数表示可能的最小周长。
示例
输入
11
输出
20
解题思路
首先可以确定的是对于任意的n，一定可以表示成为若干数字的平方和，因为一种保底的策略是n个1的平方相加。
接下来我们考虑为了能够让
最小，而等于n。一种显然的贪心策略是我们优先塞大的ai，
这是较大的ai值的平方会比较小的ai值的平方更快地减小n的值，从而最终使得a1 + a2 + ... + ak最小。
代码
Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int ans = 0;
for (int i = n; i >= 1; --i) {
while(i * i <= n) {
n -= i * i;
ans += i;
}
}
System.out.println(4 * ans);
}}
