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

AT_abc374_c [ABC374C] Separated Lunch 题解

24 人参与  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)
  • 赞助本站

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

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

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