题解：CF1118D1 Coffee and Coursework (Easy version)

Gao_zx · 2024-05-19 15:23:34 · 题解

题目大意

题目传送门

Polycarp 有 n 杯咖啡，每一杯咖啡都有一个对应的权值 a_i 。

同时，他还有 m 个任务：

每一天可以选择喝任意杯咖啡 i_1,i_2,i_3,\cdots,i_{k-1},i_k。其中，喝掉第一杯可以完成第 a_{i_1} 个任务，喝掉第二杯可以完成第 \max\{a_{i_2}-1,0\} 个任务 \cdots 喝掉第 k 杯可以完成第 \max\{a_{i_k}-k+1,0\} 个任务 。

Polycarp 想知道，至少需要多少天他才能完成这所有的 m 个任务；如若他不能完成，则输出 -1 。

思路

我们可以用模拟的方法，来暴力模拟。时间复杂度是 O(n^2) 。显然不会超时。

代码

#include<bits/stdc++.h>
using namespace std;
int a[105];
bool cmd(int x,int y){
    return x>y;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n,cmd);
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=1;j<=i;j++){
            int idx=j+i; 
            sum+=a[j];
            int id=1;
            while(1){
                if(idx>n){
                    break;
                }
                if(max(a[idx]-id,0)==0)break;
                sum+=a[idx]-id;
                idx+=i;
                id++;
            }
        }
        if(sum>=m){
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
    return 0; 
} 

很明显中间十分复杂，于是我们改了一下。 代码：

#include<bits/stdc++.h>
using namespace std;
int a[105];
bool cmd(int x,int y){
    return x>y;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n,cmd);
    for(int i=1;i<=n;i++){
        int sum = 0;
        int k = -1;
        for(int j = 1 ; j <= n ; j++){
            if((j-1)%i == 0){
                k++;
            }
            sum += max(a[j]-k,0);
        }
        if(sum>=m){
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
    return 0; 
} 

推荐习题

Coffee and Coursework (Hard Version) 需要使用二分！！！