《算法競賽·快沖300題》將于2024年出版，是《算法競賽》的輔助練習冊。
所有題目放在自建的OJ New Online Judge。
用C/C++、Java、Python三種語言給出代碼，以中低檔題為主，適合入門、進階。

題目描述

【題目描述】 現(xiàn)在有m棵栗子樹，n只松鼠在等待栗子下落。
?? 第i棵樹的第一個栗子在t[i]，之后每p[i]秒都掉落一個。
?? 現(xiàn)在松鼠們希望最終能獲得k個栗子，每只松鼠將選擇一棵栗子樹等待。
?? 不考慮松鼠移動到每棵樹的時間，只考慮等待時間。
?? 請求出最優(yōu)情況下的最少的等待時間，即松鼠選擇最優(yōu)情況下的n個栗子樹進行等待，等待時間最小是多少。
【輸入格式】 第一行為正整數(shù)m,n,k。1≤n≤m≤10000，1≤k≤10^7。
?? 第二行包含m個整數(shù)表示t[i]。
?? 第三行包含m個整數(shù)表示p[i]，1≤t[i],p[i]≤100。
【輸出格式】 輸出一個數(shù)字表示答案。
【輸入樣例】

樣例1：
3 2 5
5 1 2
1 2 1

樣例2：
3 2 5
5 1 2
1 1 1

【輸出樣例】

樣例1：
4

樣例2：
3

題解

?? 這是一道很直接的二分題。等待時間越長，掉落栗子越多，所以等待時間對應的栗子數(shù)量是單調(diào)遞增的，可以用二分法。猜一個最小等待時間x，用二分法找到x。
?? 用check(x)函數(shù)判斷x時間是否掉落超過k個栗子。首先算出m顆樹在x秒時一共掉落多少個栗子, 若栗子總數(shù)少于k, 返回false；如果超過k個，對m棵樹掉落的栗子排序后，選擇前n個與k比較。
【重點】 二分 。文章來源地址http://www.zghlxwxcb.cn/news/detail-679941.html

C++代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int t[N], p[N];
int num[N];
int n, m, k;
bool check(int x){
    for(int i = 1; i <= m; i++)  {
        if(x >= t[i])  num[i] = (x - t[i]) / p[i] + 1;
        else           num[i] = 0;
    }
    long long sum = 0;
    sort(num + 1, num + 1 + m, greater<int>());  //從大到小排序
    for(int i=1; i<=n && i<=m; i++)  sum += num[i];
    return sum >= k;
}
int main(){
    cin >> m >> n >> k;
    if(n > m)  n = m;
    for(int i=1; i<=m; i++)  cin >> t[i];
    for(int i=1; i<=m; i++)  cin >> p[i];
    int L=0, R=1e9, ans=0;
    while(L <= R){
        int mid = (L + R) >> 1;
        if(check(mid))   ans = mid, R = mid - 1;
        else             L = mid + 1;
    }
    cout<<ans<<endl;
    return 0;
}

Java代碼

import java.util.*;
public class Main {
    static int[] t = new int[10010];
    static int[] p = new int[10010];
    static int[] num = new int[10010];
    static int n, m, k;
    public static boolean check(int x) {
        for (int i = 1; i <= m; i++) {
            if (x >= t[i]) num[i] = (x - t[i]) / p[i] + 1;
            else num[i] = 0;
        }
        long sum = 0;
        Arrays.sort(num, 1, m + 1);
        for (int i=1; i<=n && i<=m; i++) sum += num[m - i + 1];
        return sum >= k;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        k = sc.nextInt();
        if (n > m) n = m;
        for (int i = 1; i <= m; i++) t[i] = sc.nextInt();
        for (int i = 1; i <= m; i++) p[i] = sc.nextInt();
        int L = 0, R = 1000000000, ans = 0;
        while (L <= R) {
            int mid = (L + R) >> 1;
            if (check(mid)) { ans = mid;  R = mid - 1; } 
            else  L = mid + 1;            
        }
        System.out.println(ans);
        sc.close();
    }
}

Python代碼

t = [0] * (10010)
p = [0] * (10010)
num = [0] * (10010)
def check(x):
    for i in range(1, m + 1):
        if x >= t[i]:  num[i] = (x - t[i]) // p[i] + 1
        else:          num[i] = 0
    num.sort(reverse=True)
    sum = 0
    for i in range(1, n+1 if n<=m else m+1):   sum += num[i]
    return sum >= k
m, n, k = map(int, input().split())
t[1:] = [int(x) for x in input().split()]
p[1:] = [int(x) for x in input().split()]
L, R, ans = 0, 1000000000, 0
while L <= R:
    mid = (L + R) // 2
    if check(mid):
            ans = mid
            R = mid - 1
    else:   L = mid + 1
print(ans)

到了這里，關于《算法競賽·快沖300題》每日一題：“松鼠與栗子”的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！