AcWing 4905. 面包店（二分答案，附数学推导）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 4905. 面包店（二分答案，附数学推导）原题链接中等

作者：

OrangeOvO , 2025-03-13 22:33:22 ·辽宁 , 所有人可见 , 阅读 337

10

1

题意

求出最小的 $x+y$ 之和，使得 $\forall a_i \times (t_c - x) + b_i \times (t_m - y) \le c_i$。

题解思路

显然，存在两个自变量 $x$ 和 $y$，我们函数图形应该是在一个三维空间上的一个曲面，求最小值显然很困难。

我们可以考虑令 $p = x + y$，则 $y = p - x$，此时带入：

$$a_i \times (t_c - x) + b_i \times (t_m - p + x) \le c_i$$

展开得到：

$$(b_i - a_i) \times x \le c_i - a_i \times t_c - b_i \times t_m + b_i \times p $$

因此，我们实际上可以把问题转化成：对于一个 $p$，能否找到一个合法的 $x$ 取值使得等式成立。

因此我们转而通过上述不等式来验证 $x$ 的值域是否合法：

钦定：$T = c_i - a_i \times t_c - b_i \times t_m + b_i \times p$

$$\left\{ \begin{aligned} x \le \frac{T}{b_i - a_i} (b_i - a_i > 0) \\ x \ge \frac{T}{b_i - a_i} (b_i - a_i < 0) \end{aligned} \right. $$

特别的，当 $b_i = a_i$ 时，若 $T < 0$，同样无解。

因此就变成农夫约翰真的种地这样维护 $x$ 值域即可。

这样，对 $p$ 二分答案即可。

tips:同样的，由于本题存在负数，向上向下取整应该使用floor和ceil函数

AC CODE

#include <bits/stdc++.h>
using namespace std;
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define endl '\n'
using i64 = long long;
constexpr int N = 2e5 + 10;

void solve()
{
    i64 n, tc, tm;
    cin >> n >> tc >> tm;
    vector<i64> a(n + 1), b(n + 1), c(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i] >> c[i];
    auto check = [&](i64 x) -> int
    {
        i64 l = max(0LL, x - tm + 1);
        i64 r = min(tc - 1, x);
        for (int i = 1; i <= n; i++)
        {
            i64 k = c[i] - a[i] * tc - b[i] * tm + b[i] * x;
            if (a[i] == b[i])
            {
                if (k < 0) return 0;
            }
            else if (b[i] - a[i] > 0)
                r = min(r, (i64)floor(k * 1.0 / (b[i] - a[i])));
            else
                l = max(l, (i64)ceil(k * 1.0 / (b[i] - a[i])));
        }
        return l <= r;
    };

    i64 l = 0, r = tc + tm - 2;
    while (l < r)
    {
        i64 mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << r << endl;
}

int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
    return 0;
}

21 评论

Jupiter_0 3天前 ·江西

谢谢佬佬刚刚一直调试不出来现在学到了

理塘の王です 2天前 ·中国香港

python版

from collections import deque, defaultdict, Counter
from functools import *
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from itertools import accumulate,permutations
#from more_itertools import distinct_permutations as dispermutations
from math import *
import sys
from typing import List
input = sys.stdin.readline
def R(): return int(input())
def RS():return input().rstrip()
def RSS():return [c for c in input().rstrip()]
def RLS():return input().rstrip().split()
def RR(): return [int(x) for x in input().split()]
def get_pre(nums): return list(accumulate(nums, initial=0))
from operator import xor,or_,and_

for _ in range(R()):
    RS()
    n,tc,tm=RR()
    nums=[]
    for _ in range(n):nums.append(RR())
    # 上下限
    l,r=0,tc+tm-2

    def cal(sum):
        # x的范围，sum次操作可以全给tm（不超过tm-1），如果有剩下的必须操作tc，sum次操作可以全部给自己 但是不能超过tc-1
        l,r=max(0,sum-(tm-1)),min(sum,tc-1)

        # 对于所有的顾客都要满足范围
        for i,j,c in nums:
            # c<=i*(tc-l)+(tm-(sum-l))*j
            # l*(j-i)<=(i*tc+tm*j-sum*j-c
            k=-(i*tc+tm*j-sum*j-c)

            # 相等，右侧要大于等于0，否则不满足条件
            if i==j:
                if k<0:return False

            elif j>i:
                r=min(r,k//(j-i))
            else:
                l=max(l,ceil(k/(j-i)))

        # 判断操作是否合法
        return l<=r
    # 二分
    while l<=r:
        mid=(l+r)>>1
        if cal(mid):
            r=mid-1
        else:
            l=mid+1
    print(r+1)

京川 3天前 ·江西

为什么用floor和不用floor结果不一样，不是会自动去掉小数部分的吗

OrangeOvO 3天前 ·辽宁

因为不用floor是向0取整，当结果为负数的时候就会向上取整了

京川 2天前 ·江西回复了 OrangeOvO 的评论

ok，感谢

Lnker 3天前 ·广东

大佬的小技巧针不辍，上次学的k*1.0这次就用上了，喜

lyy225 1天前 ·江西

这有什么问题吗？t=100那个样例显示答案错误#include[HTML_REMOVED]
using namespace std;
using ll=long long;
const int N=110;
ll ans;
int t;
ll a[N];
ll b[N];
ll c[N];
ll mm;
ll cc;
int n;
int check(ll p)
{
ll l=max(0ll,p-mm+1);
ll r=min(p,cc-1);
for(int i=1;i<=n;i)
{
ll T=c[i]-b[i]mm-a[i]cc+b[i]p;
if(a[i]==b[i])
{
if(T<0)
return 0;
}
else if(b[i]>a[i])
{
r=min(r,T/(b[i]-a[i]));
}
else
{
l=max(l,(ll)floor((1.0T/(b[i]-a[i])))+1);
}
}
return l<=r;
}
void slove()
{
cin>>n>>cc>>mm;
for(int i=1;i<=n;i)
cin>>a[i]>>b[i]>>c[i];
ll l=0;
ll r=mm+cc-2;
while(l[HTML_REMOVED]>1;
if(check(mid))
{
r=mid;
}
else
{
l=mid+1;
}
}
cout<[HTML_REMOVED]>t;
while(t–)
{
slove();
}
return 0;
}

一_33 2天前 ·四川

为什么能用二分，单调性在哪里

OrangeOvO 2天前 ·辽宁

因为操作次数越多，肯定能够满足条件，只有操作次数少于一定值，才会出现不满足条件，且低于这个阈值之后都无法满足

一_33 2天前 ·四川回复了 OrangeOvO 的评论

这样啊，谢谢大佬。大佬，你这种数学能力是怎么练出来的，我抄你代码都抄错很多次

OrangeOvO 2天前 ·辽宁回复了一_33 的评论

就是多写题，练出来的

acwing_20874 2天前 ·河北

#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
#include[HTML_REMOVED]
using namespace std;
typedef long long ll;
const int N=110;
int t;
struct ct
{
ll a,b,c;
}cts[N];
ll n,tc,tm;
bool check(ll cnt)
{
ll l1=max((ll)0,cnt-tm+1);
ll r1=min(cnt,tc-1);
for(int i=1;i<=n;i++)
{
ll a=cts[i].a;
ll b=cts[i].b;
ll c=cts[i].c;
ll k=c+bcnt-btm-atc;
if(a-b==0)
{
if(k<0) return false;
}
else if(a<b)
{
r1=min(r1,ll(ceil(k1.0/(b-a)))-1);
}
else{
l1=max(l1,ll(floor(k*1.0/(b-a)))+1);
}
}
return l1<=r1;

}
int main()
{
cin>>t;
while(t–)
{
cin>>n>>tc>>tm;
for(int i=1;i<=n;i++)
{
cin>>cts[i].a>>cts[i].b>>cts[i].c;
}
ll l=-1,r=tc+tm;
while(l+1!=r)
{
ll mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
cout<<r<<endl;