当前位置:首页 » 《资源分享》 » 正文

AT_abc374_c [ABC374C] Separated Lunch 题解

4 人参与  2024年10月10日 18:01  分类 : 《资源分享》  评论

点击全文阅读


题目传送门

右侧可以传送到原题位置。

题目大意

题目描述

由于 KEYENCE 总部的员工越来越多,他们决定将总部各部门分成两组,错开午休时间。

KEYENCE 总部有 N N N 个部门,第 i i i 个部门 ( 1 ≤ i ≤ N ) (1\leq i\leq N) (1≤i≤N) 的人数为 K i K_i Ki​ 。

将每个部门分配到 A A A 组或 B B B 组,让每个组里面的所有人在同一时间午休,并确保 A A A 组和 B B B 组的午休时间不重叠,求同一时间午休的最大人数的最小值。
换句话说,求分配给 A A A 组的部门总人数和分配给 B B B 组的部门总人数中较大者的最小值。

数据范围

2 ≤ N ≤ 20 2 \leq N \leq 20 2≤N≤20。 1 ≤ K i ≤ 1 0 8 1 \leq K_i \leq 10^8 1≤Ki​≤108。所有输入值均为整数。

解题思路

注意到数据范围比较小,可以考虑爆搜。

对于每个部门的人数 K i K_i Ki​,由于这 K i K_i Ki​ 个人只能同时在 A 组或者同时在 B 组,所以每个部门都只有两种决策:

将所有人划分在 A 组中。将所有人划分在 B 组中。

因此,我们使用 dfs 进行枚举,分别考虑第 i i i 个部门划分在 A 组与 B 组的情况。记 P A , P B P_A,P_B PA​,PB​ 分别为 A 组人数与 B 组人数,那么 a n s = max ⁡ { a n s , min ⁡ { P A , P B } } ans = \max\{ans,\min\{P_A,P_B\}\} ans=max{ans,min{PA​,PB​}},其中 a n s ans ans 代表答案。

算法总时间复杂度为 O ( 2 n ) \mathcal{O}(2^n) O(2n)。

CODE:

#include <bits/stdc++.h>using namespace std;#define int long longint k[30], ans = 1e18, n;inline void dfs(int step, int P_A, int P_B) { //正在遍历部门 step,A 组人数为 P_A,B 组人数为 P_B if (step == n + 1) {ans = min(ans, max(P_A, P_B));return;}dfs(step + 1, P_A + k[step], P_B); dfs(step + 1, P_A, P_B + k[step]);}signed main() {ios::sync_with_stdio(false);ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; i++)cin >> k[i];dfs(1, 0, 0);cout << ans;return 0;}

点击全文阅读


本文链接:http://zhangshiyu.com/post/170199.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 听了***悄悄话,所有人都让我去死番茄热门_妹妹明白掌上明珠小编推荐_小说后续在线阅读_无删减免费完结_
  • 与婳燕尔:完结+结局+番外(与婳燕尔云婳司珩:完结+结局+番外)
  • 咫尺一念间后续更新+番外_小说后续在线阅读_无删减免费完结_
  • 薛冷面(都市重生从废柴到异能王者)TXT无套路在线+无广告结局
  • 产检报告一切正常,全家却都盼着我去死结局+番外_师成安茵茵明白精校文本_小说后续在线阅读_无删减免费完结_
  • 沈毓灵踹掉言情男主,勾搭男频帝王小说(踹掉言情男主,勾搭男频帝王)前传+全书阅读新作预览
  • 改娶抓阄选中的残疾女将军后,郡主悔疯了看点十足_太后叶眠雪裴知晏宝藏文_小说后续在线阅读_无删减免费完结_
  • 高考还没开始,爸妈开始惩罚我了惊天黑幕_青青董梦竹许诺全新_小说后续在线阅读_无删减免费完结_
  • 沈时宴林初眠附加完整在线阅读(踹掉渣男后,我被闺蜜小叔宠上天)最近更新列表
  • 娇妾善撩又能生,男主为她折腰(顾熙宁)结局+番外新上热文_(顾熙宁)娇妾善撩又能生,男主为她折腰小说全文免费阅读最新章节列表笔趣阁
  • ***宝藏文_芝芝玲玲贺云章最新阅读_小说后续在线阅读_无删减免费完结_
  • 靠弹幕知道父母的兄弟穷养计划后,我成功摆脱结局_小说后续在线阅读_无删减免费完结_

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1