CF2275D.Precision Alignment
普及-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
K1o0n volunteered to work as a teaching assistant in the physics department, and he was assigned n training laboratories. In the i-th laboratory, there are three instruments; their readings are ai, bi, and ci. The instruments are distinguishable, and the order in this triple is fixed: the first (ai), the second (bi), the third (ci).
One action is to choose the index of a laboratory i and perform exactly one of the three adjustments:
- ci+=sgn(ai−bi)
- bi+=sgn(ai−ci)
- ai+=sgn(bi−ci)
Here sgn(x) equals 1 if x>0, equals −1 if x<0, and equals 0 if x=0.
In other words, an adjustment shifts the reading of one instrument by one unit, and the direction of the shift is determined by the difference of the readings of the other two, taken in the order they are written: the earlier one minus the later one.
The actions are performed one after another, and each adjustment looks at the readings that have been obtained by that moment. The same laboratory may be adjusted any number of times, and some may be left untouched altogether; in total, K1o0n is ready to make at most k actions across all laboratories.
The work will be evaluated by the worst laboratory:
S=min1≤i≤n(ai+bi+ci),
where the readings are taken after all actions. K1o0n wants to impress his colleagues, so he asks you to find the maximum S he can achieve.
K1o0n 自愿担任物理系的教学助理,被分配负责 n 个实训实验室。在第 i 个实验室中,有三台仪器,其读数分别为 ai、bi 和 ci。这些仪器彼此可区分,且该三元组中的顺序是固定的:第一个为 ai,第二个为 bi,第三个为 ci。
一次操作是指选定某个实验室编号 i,并恰好执行以下三种调整之一:
- ci+=sgn(ai−bi)
- bi+=sgn(ai−ci)
- ai+=sgn(bi−ci)
其中,sgn(x) 定义为:当 x>0 时值为 1;当 x<0 时值为 −1;当 x=0 时值为 0。
换言之,每次调整将某一台仪器的读数改变 1 个单位,而改变的方向(正向或负向)由其余两台仪器当前读数之差决定,差的计算顺序即为它们在三元组中出现的顺序:前一个减去后一个。
所有操作依次进行,每次调整所依据的读数均为截至该时刻已更新后的最新读数。同一实验室可被调整任意多次,也可能完全不被调整;总共,K1o0n 最多执行 k 次操作( across all laboratories)。
最终工作成效将由最差的实验室决定:
S=min1≤i≤n(ai+bi+ci),
式中 ai,bi,ci 均为所有操作完成后的最终读数。K1o0n 希望给同事们留下深刻印象,因此请你帮他找出他所能达到的最大可能的 S 值。
输入格式
The first line contains an integer t (1≤t≤104) — the number of testcases.
The first line of each testcase contains two integers n and k (1≤n≤2⋅105, 0≤k≤1018) — the number of laboratories and the maximum number of actions.
The next n lines of each testcase contain three integers ai, bi, and ci (−109≤ai,bi,ci≤109).
It is guaranteed that the sum of n over all testcases does not exceed 2⋅105.
第一行包含一个整数 t(1≤t≤104)——测试用例的数量。
每个测试用例的第一行包含两个整数 n 和 k(1≤n≤2⋅105,0≤k≤1018)——实验室的数量和最大操作次数。
每个测试用例接下来的 n 行,每行包含三个整数 ai、bi 和 ci(−109≤ai,bi,ci≤109)。
保证所有测试用例的 n 之和不超过 2⋅105。
输出格式
For each testcase, output one integer — the maximum achievable value of S.
Note that the answer may not fit into a 32-bit integer type. Use a 64-bit integer type (long long in C++, long in Java).
对于每个测试用例,输出一个整数——S 能达到的最大值。
注意:答案可能无法用 32 位整数类型表示,请使用 64 位整数类型(C++ 中为 long long,Java 中为 long)。
输入输出样例
输入#1
5 3 4 -3 -1 -2 1 3 5 2 4 6 3 4 6 4 2 6 7 0 7 6 0 3 1000000000000000000 4 4 4 1 5 9 -1000000000 0 1000000000 2 4 1 2 3 0 0 5 4 3 2 1 0 4 4 5 1 5 9 7 -2 1
输出#1
-2 14 12 6 6
说明/提示
In the first testcase, to obtain a minimum sum of all triples equal to −2, you need to add sgn(b1−c1)=1 to a1 four times. After that, the triplet (a1,b1,c1) will become (1,−1,−2), and the sum of the remaining triplets was originally greater than −2. It can be shown that it is impossible to obtain a sum of −1 or higher with that many operations.
In the second testcase, to obtain a minimum sum of all triples equal to 14, it is necessary to add sgn(b1−c1)=1 to a1 2 times, add sgn(a2−c2)=1 to b2 once, and add sgn(a3−b3)=1 to c3.
In the fourth testcase, it seems that it's impossible to improve the value of the second lab; however, it's not. We can make b2+=sgn(a2−c2), and we are out of the "stuck" position.
在第一个测试用例中,为了使所有三元组的最小和等于 −2,你需要对 a1 四次加上 sgn(b1−c1)=1。此后,三元组 (a1,b1,c1) 将变为 (1,−1,−2),而其余三元组的和原本就大于 −2。可以证明,使用如此多次操作无法得到 −1 或更高的和。
在第二个测试用例中,为了使所有三元组的最小和等于 14,需要对 a1 加上 sgn(b1−c1)=1 两次,对 b2 加上 sgn(a2−c2)=1 一次,并对 c3 加上 sgn(a3−b3)=1。
在第四个测试用例中,看似无法提升第二个实验室的值;但实际上并非如此。我们可以执行 b2+=sgn(a2−c2),从而摆脱“卡住”的状态。
输入解题思路,AI测评打分。不知道怎么写?