首页 > 其他分享 >acwing 4700. 何以包邮?

acwing 4700. 何以包邮?

时间:2023-01-16 14:44:43浏览次数:95  
标签:le minn 4700 int sum 样例 包邮 acwing

acwing 4700. 何以包邮?

水一期

题目描述

新学期伊始,适逢顿顿书城有购书满 $ x $ 元包邮的活动,小 $ P $ 同学欣然前往准备买些参考书。

一番浏览后,小 $ P $ 初步筛选出 $ n $ 本书加入购物车中,其中第 $ i $ 本($ 1 \le i \le n $)的价格为 $ a_i $ 元。

考虑到预算有限,在最终付款前小 $ P $ 决定再从购物车中删去几本书(也可以不删),使得剩余图书的价格总和 $ m $ 在满足包邮条件($ m \ge x $)的前提下最小。

试帮助小 $ P $ 计算,最终选购哪些书可以在凑够 $ x $ 元包邮的前提下花费最小?

输入格式

输入的第一行包含空格分隔的两个正整数 $ n $ 和 $ x $,分别表示购物车中图书数量和包邮条件。

接下来输入 $ n $ 行,其中第 $ i $ 行($ 1 \le i \le n $)仅包含一个正整数 $ a_i $,表示购物车中第 $ i $ 本书的价格。

输入数据保证 $ n $ 本书的价格总和不小于 $ x $。

输出格式

仅输出一个正整数,表示在满足包邮条件下的最小花费。

数据范围

$ 70% $ 的测试数据满足:$ n \le 15 \(; 全部的测试数据满足:\) n \le 30 $,每本书的价格 $ a_i \le 10^4 $ 且 $ x \le a_1 + a_2 + \cdots + a_n $。

输入样例1:

4 100
20
90
60
60

输出样例1:

110

样例1解释

购买前两本书 $ (20+90) $ 即可包邮且花费最小。

输入样例2:

3 30
15
40
30

输出样例2:

30

样例2解释

仅购买第三本书恰好可以满足包邮条件。

输入样例3:

2 90
50
50

输出样例3:

100

样例3解释

必须全部购买才能包邮。

dfs法

算是复习一下,优化一下能拿70

#include<iostream>
#include<cstring>
using namespace std;

const int N = 50;
#define inf 0x3f3f3f3f

int n, m;
int a[N], minn = inf;
bool flag[N];

void dfs(int now)
{
	if(now >= m)
	{
		minn = min(minn, now);
		return;
	}
	for(int i = 1; i <= n; i ++)
	{
		if(flag[i] == false)
		{
			flag[i] = true;
			dfs(now + a[i]);
			flag[i] = false;
		}
	}
}

int main()
{
	memset(flag, false, sizeof(flag));
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	dfs(0);
	cout << minn << endl;
	return 0;
}

状压法

#include<iostream>
#include<cstring>
using namespace std;

const int N = 50;
const int inf = 1e8;

int n, m;
int a[N], minn = inf;

int main()
{
	
	cin >> n >> m;
	for(int i = 0; i < n; i ++)
		cin >> a[i];

	for(int i = 0; i <= 1 << n; i ++)
	{
		int sum = 0;
		for(int j = 0; j < n; j ++)
		{
			if(i >> j & 1)
			{
				sum += a[j];
			}
		}
		if(sum >= m)
		{
			minn = min(minn, sum);
		}

	}

	cout << minn << endl;
	return 0;
}

动规法

类似于01背包,但要求选取的所有物品价值总和越小越好。01背包要求不大于某个数。

则可以转化为选取总和小于sum - x,越大越好。

#include<iostream>
#include<cstring>
using namespace std;

const int N = 50;
const int M = 3000010;
const int inf = 1e8;

int n, m, sum, re;
int a[N], minn = inf;
int v[M];

int main()
{
	
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		cin >> a[i], sum += a[i];
	re = sum - m;
	for(int i = 1; i <= n; i ++)
	{
		for(int j = re; j >= a[i]; j --)
		{
			v[j] = max(v[j - a[i]] + a[i], v[j]);
		}
	}
	
	cout << sum - v[re] << endl;
	return 0;
}

标签:le,minn,4700,int,sum,样例,包邮,acwing
From: https://www.cnblogs.com/huaziqi/p/17055356.html

相关文章

  • AcWing 786.第k个数(快速排序)
    [原链接](https://www.acwing.com/problem/content/788/题目#include<cstdio>#include<iostream>#include<cstdlib>usingnamespacestd;inta[100100];voidqu......
  • AcWing 第 86 场周赛 ABC
    https://www.acwing.com/activity/content/competition/problem_list/2794/4794.健身#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpa......
  • AcWing257 关押罪犯
    题目大意\(\qquad\)给定一张正权无向图,定义冲突值为一个集合内权值最大的边,将一张图上的点,分成两部分,不同部分的点在原图上的边作废,求最小化最大冲突值,并输出。解题思路......
  • AcWing杯 第85场周赛
    4791.死或生#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intn,ax,ay,bx,by;int32_tmain(){cin>>n;for(intt,x,......
  • ACWING 4261. 孤独的照片
    题意:给一个长度为n的只包含'G'和'H'字符串要求统计所有长度>=3且只有一个不一样的字符的子串个数思路:最开始的思路就是找到一个满足的三个字符然后向两边扩展然后......
  • ACWING 4645. 选数异或
    url:4645.选数异或-AcWing题库题意:给n个数,再给m次查询,给一个数x每次询问给一个区间l,r,问是否能从$[l,r]$中选出两个下标不同的数使得它们的异或值等于x 思路......
  • ACWING 4366. 上课睡觉
    url:4366.上课睡觉-AcWing题库题意:给n个石堆,相邻石堆可以合并现在要求每个石堆都相等,问最少合并多少次思路:由于不管咋个合并,石子数是不会变的那么就可以枚举......
  • AcWing第85场周赛
    这场周赛是手速局hh死或生某国正在以投票的方式决定2名死刑犯(编号1∼2)的生死。共有n组人员(编号1∼n)参与投票,每组10人。每组成员只参与一名死刑犯的投票,其中第......
  • AcWing杯 第 84 场周赛
    A.最大数量签到,用了结构化绑定#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intread(){...}int32_tmain(){intn=read();map......
  • AcWing395. 冗余路径
    题目大意\(\qquad\)给定一张无向图,求至少增加多少条边才能将这张图变成一个e-dcc边双连通分量。解题思路\(\qquad\)从边双的性质入手:$$边双连通分量内部的两个点之间至......