【问题描述】农场有n（1≤n≤105）堆萝卜，p[i]表示第i堆萝卜的数量（1≤p[i]≤104）。兔子到农场运萝卜，每次任选其中一堆萝卜，从中运走floor(p[i]/2)根萝卜。求解经过k（1≤k≤105）次运送后，剩余的萝卜的最小总数。 注意：1、floor(x) 表示对 x 向下取整； 2、兔子可以对同一堆萝卜进行多次运送操作。 【输入形式】两行： 第一行为n k（以空格隔开）; 第二行为每堆萝卜的数量（以空格隔开）。 【输出形式】一行，剩余萝卜的最小总数。 【样例输入】 4 3 4 3 6 7 【样例输出】 12.用c++实现

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int n,k;
int p[maxn];
bool check(int x){
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(p[i]<=x) continue;
        cnt+=(p[i]-x-1)/(x+1)+1;
    }
    return cnt<=k;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>p[i];
    int l=0,r=1e9;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}

相关问题

【问题描述】农场有n（1≤n≤105）堆萝卜，p[i]表示第i堆萝卜的数量（1≤p[i]≤104）。兔子到农场运萝卜，每次任选其中一堆萝卜，从中运走floor(p[i]/2)根萝卜。求解经过k（1≤k≤105）次运送后，剩余的萝卜的最小总数。 注意：1、floor(x) 表示对 x 向下取整； 2、兔子可以对同一堆萝卜进行多次运送操作。

这个问题可以使用贪心算法来解决。具体思路如下：

每一次运送操作，兔子应该优先选择当前数量最多的萝卜堆。这样可以保证每一次运送操作都能够尽可能地取走更多的萝卜，从而使剩余的萝卜数量尽可能地少。

因此，我们可以将所有的萝卜堆按照数量从大到小排序，然后每次选择数量最多的萝卜堆进行运送操作。具体操作方式为：取出该堆萝卜的一半，然后将其放回原处，更新堆中的数量。重复这个过程k次，最后统计剩余的所有萝卜数量即可。

下面是Python代码实现：

def min_remaining_carrots(p, k):
    p.sort(reverse=True)  # 按数量从大到小排序
    for i in range(k):
        p[0] = p[0] - p[0] // 2  # 取走一半
        p.sort(reverse=True)  # 重新排序
    return sum(p)

# 测试样例
p = [3, 4, 5, 2, 1]
k = 3
print(min_remaining_carrots(p, k))  # 输出 5

时间复杂度为$O(nlogn)$，其中n为萝卜堆的数量。