题解：CF1951D Buying Jewels

一只小菜包 · 2024-04-09 16:48:51 · 题解

这个题目的大致意思大概是这样：

爱丽丝有 n 枚硬币，她想在鲍勃的珠宝店购物。虽然鲍勃还没有开店，但他想要确保爱丽丝最终会购买恰好 k 件珠宝。为了开店，鲍勃最多可以设立 60 个摊位（每个摊位里有不限量的珠宝），并给每个摊位设置每件珠宝的价格，这个价格在 1 到 10^{18} 枚硬币之间。

幸运的是，鲍勃知道爱丽丝是贪婪的购物者：她会先去第一个摊位，尽可能多地购买珠宝，然后去第二个摊位，再尽可能多地购买，以此类推，直到最后一个摊位。了解这一点后，鲍勃可以选择设立摊位的数量，并为每个摊位设置价格，以确保爱丽丝购买到恰好 k 件珠宝。请帮助鲍勃完成这个任务，或者确定这是否不可能实现。

请注意，爱丽丝不需要花光她所有的硬币。

完整题意戳这~

结合题意，是基本贪心。我们第一次只让爱丽丝能买一个物品，剩下的钱正好可以买 m-1 的物品，这样想一下就能明白第一个摊位应该是 (n-m+1) ，这样正好能让他剩下 m-1 的钱，第二个摊位就是 1 。特判一下 n=m 。

这道题的 AC 代码

#include<bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
void solve() {  
    ll n, m;  
    cin >> n >> m;  
    if (n == m) {  
        cout << "YES" << endl << "1" << endl << "1" << endl;  
    } else if (m > (n + 1) / 2) {  
        cout << "NO" << endl;  
    } else {  
        cout << "YES" << endl << "2" << endl << (n - m + 1) << " " << 1 << endl;  
    }  
}
int main() {  
    int t;  
    cin >> t;  
    while (t--) solve();  
    return 0;  
}