ตรวจสอบว่าได้อัตราส่วนจากช่วงราคาและปริมาณที่กำหนดใน C++

แนวคิด

กำหนดช่วงราคา [lowCost, upCost] และช่วงปริมาณ [lowQuant, upQuant] ตรวจสอบว่าสามารถได้อัตราส่วน r = cost/quantity ที่ต้องการหรือไม่ โดย lowCost ≤ cost ≤ upCost และ lowQuant ≤ quantity ≤ upQuant

ตัวอย่างที่ 1

Input: lowCost=2, upCost=10, lowQuant=3, upQuant=9, r=3
Output: Yes
cost = r × quantity = 3 × 3 = 9 ∈ [2,10], quantity = 3 ∈ [3,9]

ตัวอย่างที่ 2

Input: lowCost=15, upCost=31, lowQuant=6, upQuant=13, r=8
Output: No
cost = 8 × 6 = 48 ∉ [15,31] (แม้ quantity=6 ∈ [6,13])

แนวทางแก้ปัญหา

จาก cost = quantity × r ตรวจสอบทุกค่า quantity ในช่วง [lowQuant, upQuant] คำนวณ cost = quantity × r ถ้ามี cost ใดอยู่ใน [lowCost, upCost] → Yes, มิฉะนั้น → No

โค้ดตัวอย่าง

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

bool isRatioPossible1(int lowCost1, int upCost1, int lowQuant1, int upQuant1, int r1) {
    for (int i = lowQuant1; i <= upQuant1; i++) {
        int ans1 = i * r1;
        if (lowCost1 <= ans1 && ans1 <= upCost1)
            return true;
    }
    return false;
}

int main() {
    int lowCost1 = 2, upCost1 = 10;
    int lowQuant1 = 3, upQuant1 = 9;
    int r1 = 3;
    
    if (isRatioPossible1(lowCost1, upCost1, lowQuant1, upQuant1, r1))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

ผลลัพธ์

Yes

Complexity: O(upQuant - lowQuant) สามารถปรับปรุงได้ด้วยคณิตศาสตร์: ตรวจสอบช่วง [lowQuant, upQuant] ตัดกับ [ceil(lowCost/r), floor(upCost/r)] ว่าทับกันหรือไม่ → O(1)