题解 CF1519A 【Red and Blue Beans】

· · 题解

思路分析

前置

  1. 由于每一个容器必须要有一个红色豆子和蓝色豆子，则容器最多有红色豆子和蓝色豆子的最小值个。
  2. 我们要让豆子的数量差小，就必须要尽可能地平均分配豆子。

正文

我们只需要判断制是否造一种数据满足条件即可。

开始我们最喜欢的贪心：

首先，使用红色豆子和蓝色豆子的最小值个容器，在每个容器里先放一个红豆子，一个蓝豆子，由于我们要让豆子的数量差小，就必须要尽可能地平均分配豆子。

现在，考虑一下无解的情况：

由题目以及上述分析可得：

当\frac{\max(r,b)-\min(r,b)}{\min(r,b)}>d 时无解。

\texttt{AC Code}

C++

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read_int(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            w=-1;
        } 
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
signed main(){
    int n=read_int();
    for(int i=0;i<n;i+=1){
        int r=read_int();
        int b=read_int();
        int d=read_int();
        int x=min(r,b);
        int y=max(r,b)-min(r,b);
        if(y>x*d){
            puts("NO");
            continue;
        }
        puts("YES");
    }
    return 0;
}

Python

n=int(input())
for i in range(0,n,1):
    s = input().split()
    r=int(s[0])
    b=int(s[1])
    d=int(s[2])
    x=min(r,b)
    y=max(r,b)-x
    if y>x*d:
        print("NO")
    else:
        print("YES");