「EZEC-7」Erinnerung
题目描述
小 Y 和小 Z 都是生活在 Arcaea Offline 的精灵。小 Y 有无数片落叶,其中第 i i i 片落叶的价值为 C i C_i Ci。小 Z 有无数片雪花,其中第 i i i 片雪花的价值为 E i E_i Ei。经过小 X 的仔细观察,他发现 C C C 和 E E E 满足特殊的条件:
C i = { x × i ( x × i ≤ K ) − K otherwise C_i= \begin{cases} x\times i& (x\times i\le K)\\ -K& \text{otherwise} \end{cases} Ci={x×i−K(x×i≤K)otherwise
E i = { y × i ( y × i ≤ K ) − K otherwise E_i= \begin{cases} y\times i& (y\times i\le K)\\ -K& \text{otherwise} \end{cases} Ei={y×i−K(y×i≤K)otherwise
小 Y 和小 Z 可以对这些落叶和雪花进行一些操作。每次,他们会选择满足价值之和 ≥ K \ge K ≥K 的一片落叶和一片雪花,然后让把它们一同组成一段彩色的回忆(Erinnerung)。之后,这片雪花和这片落叶就消失不见了,之后的操作也不能再用到这片雪花和落叶了。
小 X 想知道,他们最多能进行多少次操作。
输入格式
本题有多组数据。
第一行一个整数 T T T,表示数据的组数。
接下来 T T T 行,每行三个非负整数 x , y , K x,y,K x,y,K。
输出格式
对于每组数据,输出一个整数,代表最多能有多少次操作。每组数据的答案用一个换行符隔开。
样例 #1
样例输入 #1
2
2 3 10
2 4 11
样例输出 #1
3
2
样例 #2
样例输入 #2
1
0 0 1
样例输出 #2
0
提示
【数据范围】
- Subtask 1(30 points): x , y , K , T ≤ 10 x,y,K,T\le 10 x,y,K,T≤10。
- Subtask 2(70 points):无特殊限制。
对于 100 % 100\% 100% 的数据,满足 0 ≤ x , y ≤ 1 0 10 0\le x,y\le 10^{10} 0≤x,y≤1010, 1 ≤ K ≤ 1 0 10 1\le K\le 10^{10} 1≤K≤1010, 1 ≤ T ≤ 1 0 5 1\le T\le 10^5 1≤T≤105。
题解:
这道题我最开始的想法是枚举的,但是一看这数据量就知道这肯定有规律。于是就去看这个规律,那些大佬总结的我看的不是很懂,我讲讲我写的,
C数组大概是这样的
x 2x 3x … -k -k
E数组大概是这样的
y 2y 3y … -k -k
那么要是匹配的话最好就是从一个的最大开始,去对面找到最小可以匹配的数,枚举行不懂我们来看看数学规律。
假设最后一个为 nx,nx到k有多少呢,
k%x对吧,
那么对面大于k%x的最小数的系数是什么呢,
k%x/y对吧,
往后的都可以匹配那么就有 k/y-k%x/y个
但是要注意两边的个数是不等的,要取最小值
就有了 min(k / y - k % x / y, k / x - k % y / x)
然后呢要注意x,y为0的情况,还有就是x或y的倍数刚刚好就是k的时候
还有呢要注意开long long
好了上代码
#include <bits/stdc++.h>
using namespace std;
long long t, x, y, k;
int main()
{cin >> t;while (t--){cin >> x >> y >> k;if (x != 0 && y != 0)cout << min(k / y - k % x / y, k / x - k % y / x) << endl;else if (x == 0 && y != 0 && k % y == 0)cout << 1 << endl;else if (y == 0 && x != 0 && k % x == 0)cout << 1 << endl;else cout << 0 << endl;}return 0;
}