文档章节

[洛谷P1528] 切蛋糕

o
 osc_z1hvg4cu
发布于 2018/04/24 16:53
字数 888
阅读 6
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

洛谷题目链接:切蛋糕

题目描述

Facer今天买了n块蛋糕,不料被信息组中球球等好吃懒做的家伙发现了,没办法,只好浪费一点来填他们的嘴巴。他答应给每个人留一口,然后量了量每个人口的大小。Facer有把刀,可以切蛋糕,但他不能把两块蛋糕拼起来,但是他又不会给任何人两块蛋糕。现在问你,facer怎样切蛋糕,才能满足最多的人。(facer的刀很强,切的时候不会浪费蛋糕)。

输入输出格式

输入格式:

第一行n,facer有n个蛋糕。接下来n行,每行表示一个蛋糕的大小。再一行一个数m,为信息组的人数,然后m行,每行一个数,为一个人嘴的大小。(1<=n<=50, 1<=m<=1024)

输出格式:

一行,facer最多可以填多少张嘴巴。

输入输出样例

输入样例#1:
4 30 40 50 25 10 15 16 17 18 19 20 21 25 24 30

输出样例#1:
7

**简述一下题意:**给出$n$块蛋糕的大小和$m$个人要吃的量.现在只允许切蛋糕,求最多能满足多少人的需求. </br> 我们并不知道最终能满足多少人,但是很显然,肯定要优先满足需求较小的人.所以可以现将每个人的需求排个序,这样口的大小的数组就是单调的了.既然是单调的,就可以用二分来确定最多能否满足前mid个人.前mid个人能否满足直接爆搜就可以了. </br> 然而,这样并过不了,因为数据范围,这么搞是肯定要TLE的.所以我们可以考虑一下剪枝.

  • 因为口的大小是单调的,所以如果第$i$个人和第$i-1$个人的口大小相同,不能满足第$i$个人就不能满足第$i-1$个人.
  • 因为每次切都会有浪费(搜索过程中并不知道哪些一定可以作为浪费,但是如果第一个人都无法满足就一定是浪费了的),所以可以吧浪费的统计下来,那么如果蛋糕的总和减去浪费的总量小于前$mid$个人的口的大小,则不论怎么搜,都搜不出结果.
  • 然后就是在搜索的过程中可以先从第$mid$个开始往第一个搜,因为能满足第$mid$人的情况比较少,可以减少分支.
#include<bits/stdc++.h>
using namespace std;
const int N=50+5;
const int M=1024+5;

int n, m, ans = 0, waste = 0;
int cake[N], temp[N], sum = 0;
int mouth[M], pre[M];

bool dfs(int person,int pos,int mid){
    if(person == 0) return true;
    if(sum-waste < pre[mid]) return false;
    for(int i=pos;i<=n;i++){
	    if(temp[i] < mouth[person]) continue;
	    temp[i] -= mouth[person];
	    if(temp[i] < mouth[1]) waste += temp[i];
	    if(mouth[person] == mouth[person-1]){
	        if(dfs(person-1,i,mid)) return true;
	    }
	    else if(dfs(person-1,1,mid)) return true;
	    if(temp[i] < mouth[1]) waste -= temp[i];
	    temp[i] += mouth[person];
    }
    return false;
}

bool check(int mid){
    memcpy(temp,cake,sizeof(temp));
    waste = 0; bool res = dfs(mid,1,mid);
    if(res) return true;
    return false;
}

int main(){
    //freopen("data.in","r",stdin);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> cake[i], sum += cake[i];
    cin >> m;
    for(int i=1;i<=m;i++) cin >> mouth[i];
    sort(mouth+1 , mouth+m+1); sort(cake+1 , cake+n+1);
    for(int i=1;i<=m;i++) pre[i] = pre[i-1]+mouth[i];
    int l = 0, r = m, mid;
    while(pre[r] > sum) r--;
    while(l <= r){
	    mid = (l+r>>1);
	    if(check(mid)) l = mid+1, ans = mid;
	    else r = mid-1;
    }
    printf("%d\n",ans);
    return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

2020-2021 设计趋势ISUX报告 · 用户体验篇

据说点击蓝色字体关注同学都升职加薪了 前言 身为用户体验设计师,无时无刻不被世界上的新事物冲刷着认知——互联网红利下降带来变化莫测的商业动向、循着摩尔定律野蛮生长日新月异的新技术、...

静电1983
07/04
0
0
当查询的数据来自多个数据源,有哪些好的分页策略?

概述 在业务系统开发中,尤其是后台管理系统,列表页展示的数据来自多个数据源,列表页需要支持分页,怎么解决? 问题 如上图,数据源可能来自不同 DB 数据库,可能来自不同 API 接口,也可能...

新亮笔记
03/14
9
0
花最少的时间点亮OLED之RT-Thread u8g2之(DIY一个小小天气站+万年历)

准备花几天时间DIY一个小小天气站+万年历,一来可以送给好友,二来也是蹦着熟悉RT-Thread的目的去学习,以提高自己的工作效率,指不定哪天就用上了,总之技多不压身嘛! 1、什么是u8g2? u8g...

Aladdin-Wang
07/10
0
0
HTML5 不得不看的本地存储 LocalStorage

用过HTML5 本地存储和sessionStorage的,你就感觉html5很强大,比cookie和session好用很多,下面让我们来学习这个知识吧... 最早的Cookies自然是大家都知道,问题主要就是太小,大概也就4KB...

胡哥有话说
2016/08/16
0
0
Oracle SQL自动化审核工具的实现

作者介绍 梁铭图,新炬网络首席架构师,十多年数据库运维、数据库设计、数据治理以及系统规划建设经验,拥有Oracle OCM、Togaf企业架构师(鉴定级)、IBM CATE等认证,曾获dbaplus年度MVP以及...

osc_sezkegv6
15分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部