游游的正整数

[编程题]游游的正整数

热度指数：202 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游拿到了一个正整数 $a$ ，她每次操作可以选择将 $a$ 加上 $x$ ，但必须满足 $l\leq x \leq r$ 。游游希望操作结束后 $a$ 恰好等于 $b$ 。游游想知道，最少需要多少次操作，最多需要多少次操作？

输入描述:

共有组询问。
每组询问输入四个正整数。

输出描述:

对于每组询问，输出一行答案。
如果无论如何都不能让等于，则输出-1。
否则输出两个整数，分别代表最少操作次数和最多操作次数。

示例1

输入

输出

1 2
-1
2 4

说明

第一组询问，操作一次的方案：直接使加5。操作2次的方案：先加2再加3。
第二组询问，由于只能加2，显然无法使得1变成4。
第三组询问，操作2次的方案：先加3再加5（方案不唯一）。操作4次的方案：加4次2。

算法知识视频讲解

牛客175121741号

差不多就是个脑筋急转弯，用dp做成麻瓜，超时了。想通了之后很简单，注意用long就可以了

思路：记录l～r之间的距离dis，求出target/l，此时取target/l个l值，距离target可能还有remain，remain如果小于target/l * dis，则操作target/l次必然可以得到b值。不善言辞，证明就跳过了囧，实在不会说，反正就意会吧...

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



int main() {
    int t;
    cin >> t;
    while(t--) {
        long a, b, l, r;
        scanf("%ld %ld %ld %ld",&a,&b,&l,&r);
        // cin >> a >> b >> l >> r;
        long target = b - a;
        long dis = r - l;
        long most = target / l;
        long remain = target - most * l;
        if(dis * most >= remain) {
            cout << (target + r - 1) / r << ' ' << most << endl;
        }
        else cout << -1 << endl;
    }
}
// 64 位输出请用 printf("%lld")

发表于 2023-07-31 00:11:16 回复(3)

Python

yq19

n = int(input())
for _ in range(n):
    a, b, l, r = map(int, input().split())
    m = b - a

    result = [-1, -1]

    maxcnt = m // l
    
    mincnt = m // r
    if m % r != 0:
        mincnt += 1
    
    if m >= mincnt * l and m <= mincnt * r and m >= maxcnt * l and m <=maxcnt * r:
        print(mincnt, maxcnt)
    else:
        print(-1)

编辑于 2023-10-08 19:49:25 回复(0)