寒假每日一题 -- 1月5号 XTUOJ 1222 Eletronic Palse
Eletronic Palse | ||
| [ Submit Code ] [ Top 20 Runs ] [ Runs Status ] | ||
| Acceteped : 582 | Submit : 1321 | |
| Time Limit : 2000 MS | Memory Limit : 65536 KB | |
Description | ||
| 题目描述 电子脉冲A的周期为N，依次的强度为A0,…,An-1; 电子脉冲B的周期为M，依次的强度为B0,…,Bm-1; 两个电子脉冲都从时刻0开始，按周期进行发射，求第一次达到强度和最大的时刻。 输入 第一行是一个整数T(T≤1000)，表示样例的个数。 每个样例的第一行是两个整数N和M，(1≤N,M≤1000)。 第二行是N个整数，表示A脉冲的强度。 第三行是M个整数，表示B脉冲的强度。 强度值处于[1,100]。 输出 每行输出一个样例的结果，包括4个值，依次为第一次出现最大强度和的时刻， 最大强度和，脉冲A的强度，脉冲B的强度。 样例输入 2 3 4 1 2 3 1 2 3 4 4 6 3 1 2 1 1 2 1 3 1 4 样例输出 11 7 3 4 5 5 1 4 提示 巨大的输入输出，请使用C风格的输入输出 | ||
这个题只要能理解题意应该就不太难，抓住“周期”这两个字就行了
思路
- 首先理解题意，抽象一下就是两段数组可以不断重复，要求出两个【循环数组】【相同下标对应值之和】的【最大值】
- 由题两个数组的长度分别为n和m，可以很简单的得出在两循环数组长度到了lcm(m, n)就会出现重复的情况，画个图可以很简单看出来
3. 接下来遍历这lcm(m, n)种情况即可，由于本质上就是在不断重复遍历两个数组求相同下标值之和，所以可以用到取余这个操作，这种遍历循环数组的小技巧很有用
一循环数组，这个循环数组由不断重复长度为【n】的数组（把它叫做基数组）组成
循环数组中下标为【idx】的元素就对应基数组中下标为【idx % n】的元素
代码
#include
#define N 1005
int A[N] = {0};
int B[N] = {0};
int max(int a, int b) {return a ? a > b : a;
}
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {int t = a * b / gcd(a, b);return t;
}int main() {int k;scanf("%d", &k);while (k--) {int n, m, i1, i2;scanf("%d%d", &n, &m);int pos = 0;int max = 0;for (int i = 0; i < n; i++) {scanf("%d", &A[i]);}for (int i = 0; i < m; i++) {scanf("%d", &B[i]);}int num = lcm(n, m); // 最大公因数 for (int i = 0; i < num; i++) {if (A[i % n] + B[i % m] > max) {pos = i;max = A[i % n] + B[i % m];i1 = A[i % n];i2 = B[i % m];}}printf("%d %d %d %d\n", pos, max, i1, i2);}
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！