题目

奶牛晒衣服

题目背景

熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿，为牛宝宝晒衣服就成了很不爽的事情。于是，熊大妈请你（奶牛）帮助她完成这个重任。

题目描述

一件衣服在自然条件下用一秒的时间可以晒干 $a$ 点湿度。抠门的熊大妈只买了一台烘衣机 。使用用一秒烘衣机可以让一件衣服额外烘干 $b$ 点湿度（一秒晒干 $a+b$ 湿度），但在同一时间内只能烘一件衣服。现在有 $n$ 件衣服，第 $i$ 衣服的湿度为 $w_i$（保证互不相同），要你求出弄干所有衣服的最少时间（湿度为 $0$ 为干 ）。

输入格式

第一行三个整数，分别为 $n,a,b$。
接下来 $2$ 到 $n+1$ 行，第 $i$ 行输入 $w_i$。

输出格式

一行，弄干所有衣服的最少时间。

样例 #1

样例输入 #1

3 2 1
1
2
3

样例输出 #1

1

提示

样例解释

让机器烘第三件衣服即可一秒完成。

数据范围

$1 \le w_i,a,b,n \le 5 \times 10^5$

代码

#include<bits/stdc++.h>
using namespace std;

//题中数据
int n,a,b;

//湿度
int w[500020];

//二分数据
int Left,Right,mid;

//二分检查
bool check(int ans)
{

    //替换
    int inw[500020];

    //需要的烘烤时长
    int num=0;

    for(int i=1;i<=n;i++)
    {
        inw[i]=w[i];

        inw[i]-=a*ans;
    }

    /*for(int i=1;i<=n;i++)
    {
        cout<<inw[i]<<" ";
    }

    cout<<endl;*/

    for(int i=1;i<=n;i++)
    {
        if(inw[i]>0)
        {
            num+=inw[i]/b;

            if(inw[i]%b!=0)
            {
                num++;
            }

        }
        if(num>ans) return false;

    }

    return true;
}

int main()
{

    //读入
    cin>>n>>a>>b;  
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        Right=max(Right,w[i]);
    }

    //初始化二分数据
    Left=1;

    //二分
    while(Left+1<Right)
    {
        mid=(Left+Right)>>1;

        if(check(mid))
        {
            Right=mid;
        }

        else
        {
            Left=mid;
        }
    }

    cout<<Right<<endl;

    system("pause");//VScode所需 可无视
    return 0;
}

记录

AC记录

过不了的样例

输入

3 2 1
1
2
3

输出

1