蓝桥杯备考冲刺必刷题（C++） | 3792 小蓝的礼物

学习C++从娃娃抓起！记录下蓝桥杯备考比赛学习过程中的题目，记录每一个瞬间。

附上汇总贴：蓝桥杯备考冲刺必刷题（C++） | 汇总-CSDN博客

【题目描述】
小蓝想要给她的女朋友小桥买一份生日礼物，她来到了一家礼品店。在店里，她看中了 N N N件物品，每件物品都有一个价格 A i A_i Ai​。
小蓝手中有 K K K元钱和一张50%的折扣券，可以在购买任意一件物品时使用。使用折扣券后，购买该物品的价格为原价的一半向上取整。
对于一件价值为 X X X的物品，当小蓝使用折扣券后，他只需要花费 ⌈ x 2 ⌉ \lceil \frac{x}{2} \rceil ⌈2x​⌉元即可带走该商品。
请帮助小蓝确定，在使用折扣券的情况下，她最多能够购买多少件物品送给小桥作为生日礼物。
【输入】
第一行是两个整数 N N N和 K K K，分别表示物品的数量和小蓝手中的预算。
接下来一行是 N N N个整数，表示每个物品的价格 A i A_i Ai​。
【输出】
输出一个整数，表示在使用折扣券的情况下，小蓝最多可以购买多少件物品作为生日礼物。
【输入样例】

5 10
3 1 3 4 5

【输出样例】

4

【代码详解】

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k, a[100005], ans;
signed main()
{
    cin >> n >> k;
    for (int i=1; i<=n; i++) {  // 输入n件物品
        cin >> a[i];
    }
    sort(a+1, a+n+1);  // 按照从小到大排序
    int mark = 1;  // 定义下标，起始为1
    while (k-a[mark]>=0 && mark<n) {  // 当手中的钱还够买a[mark]物品时，且mark不越界
        ans += a[mark];  // 总费用增加（其实不用输出总费用）
        k -= a[mark];  // 手中的钱减少
        mark++;  // 下标自增1
    }
    if (k-((a[mark]+1)/2)>=0) {  // 尝试能否用50%的折扣券买a[mark]物品（这里不用ceil，而是(a[i]+1)/2）
        cout << mark << endl;  // 输出mark
    } else {
        cout << mark-1 << endl;  // 否则输出mark-1
    }
    return 0;
}

【运行结果】

5 10
3 1 3 4 5
4