[ICPC2016 WF]Balanced Diet

题目链接:https://www.luogu.com.cn/problem/P6917

题目描述

每天,Danny 都会从糖果店买一颗糖并吃掉它。糖果店中有 mm 种糖,编号为 1 \dots m

Danny 知道均衡饮食很重要,他正在尝试在购买糖果时有一个均衡的饮食。因此他给每种糖 i 分配了一个目标分数 f_i (0 \le f_i \le 1,f_i 为一个实数 ), 。他希望他所吃的所有糖中,第 i 种糖的数量占比大概为 f_i

准确的说, 令 s_ i 表示 Danny 已经吃掉的第 i 种糖的数量, n = \sum _{i=1}^ m s_ i, 我们认为一种吃糖的方法是均衡的仅当对于所有的 i,满足:

nf_i-1<s_i<nf_i+1

Danny 已经购买并吃掉了一些糖,并且他保证每个前缀的饮食都是均衡的。他想知道在保证每个前缀均衡饮食的条件下,他最多还能吃多少颗糖。

给定目标分数 f_i 和他已经吃过的糖果序列,请你确定在保证每个前缀均衡饮食的条件下,Danny 最多还能购买并吃掉多少颗糖果。

Solution

这道题我自己思考出有价值的东西很少…….

首先可以发现,由于 s_i 为整数,所以 n f_ i – 1 可以改造为 \lfloor n f_ i \rfloor \le s_ i \le \lceil n f_ i \rceil

故当 nf_i 为整数 时,s_i 只有 1 个取值,否则可以取 2 个值。

S=\sum a_i,当吃掉糖果的个数 nS 的整倍数时,所有 s_i 都是确定的。(因为所有 nf_i 都是整数)

只要吃到 S 天,我们就可以吃到 forever 。(每 S 天,吃第 i 种糖果 a[i] 个)

因为每个前缀都保证合法,所以我们对 n 可以取 n\bmod S

同样的,前 k 天吃了第 i 个糖果的个数 s[i] 也都可以取 s[i]\bmod a[i]

如果要暴力计算每天该吃什么糖果,复杂度是 O(S*n)

我们只用计算每种糖果(记作 i ),对于每个 1 \to a[i] 的每个糖果数量 j,在第 t 天必须要达到,也就是 t 天后必须要吃够 j 个这种糖果

然后就算出对于每个 j ,哪一天达到。然后统计一下满不满足即可。

至于上界 \lceil n f_ i \rceil,因为我们是贴着下界走的,所以不会超上界的。

也可以看看这份题解 https://blog.csdn.net/l_0_forever_lf/article/details/80455946

#include<bits/stdc++.h>
const int N = 3e5+10;
int n,k;
int a[N],t[N],S,cnt[N];
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]),S+=a[i];
    for(int i=1;i<=k;++i){
        int x;
        scanf("%d",&x);
        t[x]++;
    }
    for(int i=1;i<=n;++i)   t[i]-=a[i]*(k/S);
    k=k%S;
    for(int i=1;i<=n;++i){
        //std::cerr<<i<<" ";
        for(int p=1;p<=a[i];++p){
            if(t[i]){t[i]--;continue;}
            int j=(int)(std::ceil(1.0*p*S/a[i]));
            cnt[j]++;
        }
    }
    int x=0;
    for(int i=k+1;i<=S;++i){
        x++;
        x-=cnt[i];
        if(x<0) {
            printf("%d\n",i-1-k);
            return 0;
        }
    }
    puts("forever");
    return 0;
}
分类: 思维贪心

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注