首页 > 其他分享 >题解:AT_abc374_c [ABC374C] Separated Lunch

题解:AT_abc374_c [ABC374C] Separated Lunch

时间:2024-10-07 10:11:58浏览次数:9  
标签:cnt ch group int 题解 sum dfs Lunch abc374

无耻的广告更好的阅读体验~

最近在搞个人博客博客园的差点忘了更了。


已经沦落到在写这种水题题解了。

题目翻译

有 \(n\) 队人,每个队人数不同,把他们分成 2 组(同一队的不能拆开),使两组人数差距尽量小。

形式化题意:有 \(n\) 个数,把它们分成两组,使两组和的差尽量小。

说句闲话:感觉这题目很经典,但我没有原题作为证据(大雾

解法

本来觉得我这菜鸡实力是不可能做出来的,已经准备摆烂了,此时我突然发现 \(n \le 20\)。

这是啥概念?

时间复杂度对应表

看图,\(n \le 25\) 都是可以用 \(O(2 ^ n)\) 做法解决的,这不结束了?直接枚举每一组,分类讨论是 A 组还是 B 组,就可以了。

给个小建议:可以记录总人数,这样子只需要记录 A 组人数,B 组人数可以直接 \(O(1)\) 计算,这样就变成选与不选的 dfs 模板题目了……更关键的是这样子不需要记录为每一队对应哪一组了。

代码

ACCode with 注释
/*Code by Leo2011*/
#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define EPS 1e-8
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
#define log printf
#define IOS                      \
	ios::sync_with_stdio(false); \
	cin.tie(nullptr);            \
	cout.tie(nullptr);

using namespace std;

typedef __int128 i128;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 30;
int n, a[N], ans = INF, sum;

template <typename T>

inline T read() {
	T sum = 0, fl = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

template <typename T>

inline void write(T x) {
	if (x < 0) {
		putchar('-'), write<T>(-x);
		return;
	}
	static T sta[35];
	int top = 0;
	do { sta[top++] = x % 10, x /= 10; } while (x);
	while (top) putchar(sta[--top] + 48);
}

void dfs(int group, int cnt) {
	if (group == n) {
		ans = min(ans, max(cnt, sum - cnt));
		return;
	}
  // 组 A
	dfs(group + 1, cnt + a[group]);
  // 组 B
	dfs(group + 1, cnt);
}

int main() {
	n = read<int>();
	FOR(i, 1, n) a[i] = read<int>(), sum += a[i];
	dfs(1, 0);
	write<int>(ans);
	return 0;
}
// 20组---》爆搜挂着机,打表出 AC

赛时 AC 记录~

理解万岁!

标签:cnt,ch,group,int,题解,sum,dfs,Lunch,abc374
From: https://www.cnblogs.com/leo2011/p/18449796

相关文章

  • P3527 MET-Meteors 题解
    Solution单次二分:二分时间,做这个时间前的所有操作,然后线性统计。注意到可以整体二分,直接整体二分是\(O(n\log^2n)\)。考虑扫描序列,用线段树维护每个时间段内该位置的增加值,差分一下可以实现。将这棵线段树持久化一下,一个国家所有位置同时二分即可\(O(n\logn)\),可惜空间太......
  • P3250 网络 题解
    Solution单次二分:问“重要度\(\gex\)的所有操作,且\(t\)时间点还存在的所有操作中,是否有不经过这个点的”整体二分:保持操作、询问按时间有序,即预先按时间排序,下传时保持有序;对于一次Solve,对于所有重要度\(\gemid+1\)的操作(加入、删除),考虑与询问按时间混合排序,然后依次......
  • P3215 括号修复 题解
    Statement维护一个括号序列,有以下操作:区间覆盖区间翻转区间反转(左括号变右括号,右括号变左括号)区间问最少改多少位能使括号序列合法,保证有解Solution单纯没想到答案怎么算。。。首先一段括号序,如果消除中间的所有匹配,最终一定形如))))(((,这个信息是可合并的设这时左括......
  • P5416 = UOJ 198 时空旅行 题解
    Statement一棵树,每个节点上有一个集合,每个儿子集合由父亲集合增加一个点\((x_i,c_i)\)或删除一个点得到。根节点集合为\(\{(0,0,0,c_0)\}\)多次询问,每次问\(u\)点的集合内,\(\min\{(x_i-x)^2+c_i\}\)Solution首先你认真读完题发现原题中\(y,z\)都是没用的然后离线DFS......
  • 火星商店问题 题解
    Solution线段树套trie,秒了!\(O(n\log^2n)\)Code#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=1e5+......
  • Gym 100543G Virus synthesis 题解
    Solution首先只考虑回文串的答案;我们重点考虑的是偶回文串结论:对于偶回文串\(u\),从其最长的长度小于等于他的一半的回文后缀,或其父亲转移过来,一定是最优的证明:设\(u\)的一个回文子串为\(v\)(不是父亲),你要让\(v\tou\)的转移最优首先\(v\)不能跨过\(u\)的中点,因为此......
  • LOJ 6041 事情的相似度 题解
    Statement先把串reverse,多次给\(l,r\),求\[\max_{l\lei<j\ler}\{\text{LCP}(i,j)\}\]Solution\(\text{sqrtlog}\sim\text{sqrt}\):莫队+线段树/树状数组/set,用SA做\(nm/\omega\):bitset乱搞\(\log^2\):SAM+LCT+BIT在parent树上,LCP等于LCA的......
  • P3332 K大数查询 题解
    Solution整体二分板子题vector太好写了111#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<=(k);++i)#definereo(i,j,k)for(inti=(j);i>=(k);--i)typedeflonglongll;constintN=50010;intn,m,ans[......
  • P4093 序列 题解
    Statement给出\(n\) 个数的序列\(\{a_i\}\),接下来\(m\)秒中每一秒会有一个数发生变化,然后恢复。问最长的子序列长度,使得任意时刻这个子序列不下降。\(n\le10^5\)Solution设\(b_i\)为\(i\)最小能变成的数,\(c_i\)为\(i\)最大能变成的数\[f(i)=\max_{j<i\landc......
  • P4690 镜中的昆虫 (动态区间颜色数) 题解
    Statement区间涂颜色区间颜色数Solution\(O(\text{polysqrt})\)略。\(O(\text{polylog})\)颜色段均摊有两层含义:随机数据下:任意时刻的颜色段个数期望\(O(\logn)\)非随机数据下:每次推平时访问的颜色段个数均摊\(O(n)\)首先维护每个点\(i\)的\(pre_i\),一次询......