CSP 202209-2 何以包邮？ C++ 70

2023-01-07

题目

【题目描述】新学期伊始，适逄顿顿书城有购书满x元包邮的活动，小P同学欣然前往准备买些参考书。一番浏览后，小P初步筛选出 n 本书加入购物车中，其中第 i 本（1≤i≤n)的价格为 ai 元。考虑到预算有限，在最终付款前小P决定再从购物车中删去几本书（也可以不删），使得剩余图书的价格总和m在满足包邮条件(m≥x)的前提下最小。试帮助小P计算，最终选购哪些书可以在凑够x元包邮的前提下花费最小？

【输入格式】从标准输入读入数据。输入的第一行包含空格分隔的两个正整数 n 和 x ,分别表示购物车中图书数量和包邮条件。接下来输入 n 行，其中第 i 行(1≤i≤n)仅包含一个正整数 ai ,表示购物车中第 i 本书的价格。输入数据保证 n 本书的价格总和不小于 x 。

【输出格式】输出到标准输出。仅输出一个正整数，表示在满足包邮条件下的最小花费。

【样例输入】

【样例输出】

代码

#include <bits/stdc++.h>

using namespace std;
using ll=long long;
const ll N=35;
static ll n,x,minsum=12e5;

bool cmp(ll a,ll b)
{
    return b<a;
}

int buy(ll i,ll sum,ll a[N])
{
    if(i+1<n)
    {
        buy(i+1,sum,a);
        sum+=a[i];
        if(sum<minsum&&sum>=x)
            minsum=sum;
        buy(i+1,sum,a);
    }
    else
    {
        sum+=a[i];
        if(sum<minsum&&sum>=x)
            minsum=sum;
    }
    return 0;
}

int main()
{
    ll a[N];//price
    ll sum=0;
    cin>>n>>x;

    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n,cmp);
    buy(0,sum,a);
    cout<<minsum<<endl;

    return 0;
}