首页 > 其他分享 >题解:AT_abc362_c [ABC362C] Sum = 0

题解:AT_abc362_c [ABC362C] Sum = 0

时间:2024-07-13 22:40:34浏览次数:15  
标签:10 ch ll 题解 Sum top ABC362C sum left

很好写(15 min 解决)但不好讲(跟别人讲了 20 min)的写法 QwQ……


首先,咱先算出原式的范围。最小值(暂且记为 \(k\))的公式就是:

\[k = \sum_{i = 1}^{N} L_i \]

就是每一个最小可能值的和。

同理,最大值(我记为 \(w\))的公式就是:

\[w= \sum_{i = 1}^{N} R_i \]

即最大可能值的和。

算这玩意儿有啥用呢?卡区间!

你说要是 \(k > 0\) 或者 \(w < 0\),即最小都比 \(0\) 大或者最大都不到还能干成 \(0\) 吗?肯定不能啊!这种情况就是 No

剩下的鉴于大家都是整数,而且可以随便变化,一定是 Yes

所以该咋构造呢?

我们可以以 \(k\) 为基准,往 \(0\) 去凑。

具体来讲,就是:

\[Ans_i = \begin{cases}R_i(left > R_i - L_i) \\ L_i + left(R_i \ge left + L_i)\end{cases} \]

其中 \(left\) 表示到 \(0\) 的距离,也就是 \(0 - k\)。说人话翻译一下就是:

  1. 能够直接凑完,那就直接凑完,然后就不用凑了。
  2. 凑不完,能凑多少是多少,记得更新一下后面要凑的数目

比如样例 \(1\):

经计算,\(left = 3\) ,第一组(\(3 \sim 5\))最多凑个 \(2\),那就凑 \(2\),输出 \(5\),还剩个 \(1\) 要凑。第二组(\(-4 \sim 1\))最多能凑个 \(5\),但 \(1\) 就够了,输出 \(-3\),不用凑了。最后一组,不用凑了,直接输出 \(-2\)。

算一下,\(5 + (-3) + (-2) = 5 - 3 - 2 = 0\),满足条件。

注:今天,你开 long long 了吗?


ACCode:

// Problem: C - Sum = 0
// Contest: AtCoder - Toyota Programming Contest 2024#7(AtCoder Beginner Contest 362)
// URL: https://atcoder.jp/contests/abc362/tasks/abc362_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*Code by Leo2011*/
#include <bits/stdc++.h>

#define log printf
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define FOR(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
#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<ll, ll> PII;

const ll N = 2e5 + 10;
ll n, l[N], r[N], lft, suml, sumr;

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];
	ll top = 0;
	do { sta[top++] = x % 10, x /= 10; } while (x);
	while (top) putchar(sta[--top] + 48);
}

int main() {
	n = read<ll>();
	FOR(i, 1, n) l[i] = read<ll>(), r[i] = read<ll>(), suml += l[i], sumr += r[i];
	if (!(suml <= 0 && sumr >= 0)) {
		cout << "No";
		return 0;
	}
	lft = 0 - suml;	 // 到0剩下的距离
	cout << "Yes" << endl;
	FOR(i, 1, n) {
		if (l[i] + lft <= r[i]) {
			cout << l[i] + lft << " ";
			lft = 0;
		} else {
			cout << r[i] << " ";
			lft -= r[i] - l[i];
		}
	}
	return 0;
}

理解万岁!

标签:10,ch,ll,题解,Sum,top,ABC362C,sum,left
From: https://www.cnblogs.com/leo2011/p/18300864

相关文章

  • 【题解】洛谷 P10765 「CROI · R2」在相思树下 I
    I题意简述共\(T\)组测试数据。对于每一组测试数据,有初始数列,共\(n\)个元素,从\(1\)至\(n\)。给出\(k\)次操作。操作一:将数列中下标为奇数的数全部删除;操作二:将数列中下标为偶数的数全部删除。完成操作之后,将剩余的数从下标\(1\)开始依次重新编排下标。求问\(k\)次......
  • 南京大学计算理论之美 (Summer 2024)暑期学校游记
    day-nzero4338和我说有这么个暑校,报名了day0到了钟山风雨地,石头城下水南京到了南京大学(仙林校区),被硬件震撼了一波和zero4338两人互相贩卖焦虑:为啥还没预习这个,也没预习那个到了南京大学(鼓楼校区),和同学转鼓楼校区,和同学和zero4338和同学吃饭回酒店之后说预习预习,但是......
  • 题解:Codeforces CF1613C Poisoned Dagger
    标签:二分题意给定一个长度为\(n\)的序列\(a\),定义数\(k\),对于\(i>1\),如果\(a_i-a_{i-1}<k\),\(s\)加上\(a_i-a_{i-1}\),否则加上\(k\),求满足\(s\geqh\)的最小\(k\)。思路手玩样例,\(k\)越大龙死的越快,所以具有单调性,考虑二分答案。每次缩小范围时判断是否\(k\g......
  • 洛谷 P6522 [CEOI2010 day2] tower 题解
    [CEOI2010day2]tower题目背景古巴比伦人决定建造一座塔。题目描述这座塔共有\(n\)层,每层由一个边长为\(a_i\)的立方体石块构成。一个石块\(i\)能够直接放在石块\(j\)上当且仅当\(a_i\leqa_j+D\),其中\(D\)为一个给定的常数。你需要求出如果使用全部的石块,有多......
  • D2. Sum over all Substrings (Hard Version)
    原题链接题解code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lldp[1000005]={0};voidsolve(){lln,ans=0;cin>>n;strings;cin>>s;s=""+s;//使字符串1索引化for(lli=1......
  • 洛谷 P2478 [SDOI2010] 城市规划 题解
    题意简述仙人掌上求至少间隔两个位置的最大独立集。(仙人掌指,没有一条边在两个或以上的环里的无向图。)题目分析仙人掌就是树套环,即树上每个结点都是一个结点或环。那么将题目拆解成树上DP和环上DP即可。用tarjan缩点即可。树上DP先来看看树上DP。显然每个点有三个状......
  • [ZJOI2006] 三色二叉树 题解
    [ZJOI2006]三色二叉树题解link趣题。首先我们把题目分成两部分:建树和dp求解。建树:观察发现,字符串中的第\(i\)个字符就代表图中的第\(i\)个节点。如果\(S_i=0\),直接跳过;如果\(S_i=1\),那么\(i+1\)是\(i\)唯一的子节点,在两点之间连边,然后继续递归建树即可。......
  • 2024年06月CCF-GESP编程能力等级认证C++编程三级真题解析
    本文收录于专栏《C++等级认证CCF-GESP真题解析》,专栏总目录:点这里。订阅后可阅读专栏内所有文章。一、单选题(每题2分,共30分)第1题小杨父母带他到某培训机构给他报名参加CCF组织的GESP认证考试的第1级,那他可以选择的认证语言有()种。A.1B.2C.3D.4答案:C第2......
  • Codeforces Round 957 (Div. 3) A-G 题解
    CodeforcesRound957(Div.3)A-G题解A.OnlyPluses枚举思路:枚举\(a\),\(b\),\(c\)增加的次数,维护最值即可。代码:#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#......
  • 初等数论课程测试题解
    初等数论课程测试题解刚想起来传到博客园上面。正在写。Upd.20240222:已写完,欢迎查错!一、请给出整除的概念及性质对于整数\(a,b\)\((b\neq0)\),如果存在整数\(c\),使得\(a=bc\),则称\(b\)整除\(a\),记作\(b\mida\);否则称\(b\)不整除\(a\),记作\(b\nmida\)。性质......