6323. 将钱分给最多的儿童
给你一个整数 money ，表示你总共有的钱数（单位为美元）和另一个整数 children ，表示你要将钱分配给多少个儿童。
你需要按照如下规则分配：
所有的钱都必须被分配。
每个儿童至少获得 1 美元。
没有人获得 4 美元。
请你按照上述规则分配金钱，并返回 最多 有多少个儿童获得 恰好 8 美元。如果没有任何分配方案，返回 -1 。
示例 1：
输入：money = 20, children = 3
输出：1
解释：
最多获得 8 美元的儿童数为 1 。一种分配方案为：
- 给第一个儿童分配 8 美元。
- 给第二个儿童分配 9 美元。
- 给第三个儿童分配 3 美元。
没有分配方案能让获得 8 美元的儿童数超过 1 。
示例 2：
输入：money = 16, children = 2
输出：2
解释：每个儿童都可以获得 8 美元。
提示：
1 <= money <= 200
2 <= children <= 30解答：分类讨论
class Solution {
public int distMoney(int m, int c) {
//每人先分一元
m-=c;
//不够分
if(m<0)return -1;
int res=Math.min(m/7,c);
c-=res;
m-=res*7;
//孩子没了，钱还有剩余
if(c==0&&m>0)res--;
//孩子还有一个，钱剩余3，不能有4
if(c==1&&m==3)res--;
//孩子超过两个，直接返回答案
return res;
}
}2592. 最大化数组的伟大值
给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。
定义 nums 的 伟大值 为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标数目。
请你返回重新排列 nums 后的 最大 伟大值。
示例 1：
输入：nums = [1,3,5,2,1,3,1]
输出：4
解释：一个最优安排方案为 perm = [2,5,1,3,3,1,1] 。
在下标为 0, 1, 3 和 4 处，都有 perm[i] > nums[i] 。因此我们返回 4 。
示例 2：
输入：nums = [1,2,3,4]
输出：3
解释：最优排列为 [2,3,4,1] 。
在下标为 0, 1 和 2 处，都有 perm[i] > nums[i] 。因此我们返回 3 。
提示：
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9解答：Set+哈希表
class Solution {
public int maximizeGreatness(int[] nums) {
int res=0;
TreeSet<Integer> list=new TreeSet<>();
Map<Integer,Integer> map=new HashMap<>();
for (int n:nums){
list.add(n);
map.put(n,map.getOrDefault(n,0)+1);
}
for(int i=0;i<nums.length;i++){
int n=nums[i];
Integer ceil = list.ceiling(n+ 1);
if (ceil != null) {
if(map.get(ceil)>1){
map.put(ceil,map.get(ceil)-1);
}
else{
list.remove(ceil);
}
res++;
}
}
return res;
}
}6351. 标记所有元素后数组的分数
给你一个数组 nums ，它包含若干正整数。
一开始分数 score = 0 ，请你按照下面算法求出最后分数：
从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。
将选中的整数加到 score 中。
标记 被选中元素，如果有相邻元素，则同时标记 与它相邻的两个元素 。
重复此过程直到数组中所有元素都被标记。
请你返回执行上述算法后最后的分数。
示例 1：
输入：nums = [2,1,3,4,5,2]
输出：7
解释：我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：[2,1,3,4,5,2] 。
- 2 是最小未标记元素，所以标记它和左边相邻元素：[2,1,3,4,5,2] 。
- 4 是仅剩唯一未标记的元素，所以我们标记它：[2,1,3,4,5,2] 。
总得分为 1 + 2 + 4 = 7 。
示例 2：
输入：nums = [2,3,5,1,3,2]
输出：5
解释：我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：[2,3,5,1,3,2] 。
- 2 是最小未标记元素，由于有两个 2 ，我们选择最左边的一个 2 ，也就是下标为 0 处的 2 ，以及它右边相邻的元素：[2,3,5,1,3,2] 。
- 2 是仅剩唯一未标记的元素，所以我们标记它：[2,3,5,1,3,2] 。
总得分为 1 + 2 + 2 = 5 。
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6解答：优先队列+标记数组
class Solution {
public long findScore(int[] nums) {
int n=nums.length;
boolean[] visit=new boolean[n];
PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]==b[0]?a[1]-b[1]:a[0]-b[0]);
for(int i=0;i<n;i++){
pq.offer(new int[]{nums[i],i});
}
long res=0;
while(pq.size()>0){
while(pq.size()>0&&visit[pq.peek()[1]])pq.poll();
if(pq.size()==0)break;
int[] cur=pq.poll();
int a=cur[0],b=cur[1];
res+=a;
visit[b]=true;
if(b-1>=0){
visit[b-1]=true;
}
if(b+1<n){
visit[b+1]=true;
}
}
return res;
}
}6325. 修车的最少时间
给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
同时给你一个整数 cars ，表示总共需要修理的汽车数目。
请你返回修理所有汽车 最少 需要多少时间。
注意：所有机械工可以同时修理汽车。
示例 1：
输入：ranks = [4,2,3,1], cars = 10
输出：16
解释：
- 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。
- 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。
- 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。
- 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
16 分钟是修理完所有车需要的最少时间。
示例 2：
输入：ranks = [5,1,8], cars = 6
输出：16
解释：
- 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。
- 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
- 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。
16 分钟时修理完所有车需要的最少时间。
提示：
1 <= ranks.length <= 10^5
1 <= ranks[i] <= 100
1 <= cars <= 10^6解答：二分查找
class Solution {
public long repairCars(int[] ranks, int cars) {
long l=0,r=(long)1e18;
while(l+1<r){
long mid=(r-l)/2+l;
if(check(mid,ranks,cars)){
r=mid;
}
else l=mid;
}
return r;
}
/*
t=r*n*n;
n=sprt(t/r);
*/
boolean check(long t,int[] ranks,int cars){
long res=0;
for(int r:ranks){
res+=Math.floor(Math.sqrt(t/r));
}
return res>=cars;
}
}
