ZOJ 4025 King of Karaoke

Description:

It’s Karaoke time! DreamGrid is performing the song Powder Snow in the game King of Karaoke. The song performed by DreamGrid can be considered as an integer sequence $D_1,D_2,\dots \dots ,D_n$ , and the standard version of the song can be considered as another integer sequence $S_1,S_2,\dots \dots ,S_n$ . The score is the number of integers i satisfying $1\le i\le n$ and $S_i=D_i$ .

As a good tuner, DreamGrid can choose an integer (can be positive, 0, or negative) as his tune and add to every element in . Can you help him maximize his score by choosing a proper tune?

Input:

There are multiple test cases. The first line of the input contains an integer T (about 100), indicating the number of test cases. For each test case:

The first line contains one integer n ( $1\le n\le 10^5$ ), indicating the length of the sequences D and S.

The second line contains n integers $D_1,D_2,\dots \dots ,D_n$ ( $-10^5\le D_i\le 10^5$ ), indicating the song performed by DreamGrid.

The third line contains n integers $S_1,S_2,\dots \dots ,S_n$ ( $-10^5\le S_i\le 10^5$ ), indicating the standard version of the song.

It’s guaranteed that at most 5 test cases have n > 100.

Output:

For each test case output one line containing one integer, indicating the maximum possible score.

Sample Input:

2 4 1 2 3 4 2 3 4 6 5 -5 -4 -3 -2 -1 5 4 3 2 1

Sample Output:

3 1

题目连接

将两个序列作差之后对差值计数，出现最多的差值的次数即为最大得分，输出结果。这里用map计数很好用。

AC代码:

#include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pb push_back typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> P; const int INF = 0x3f3f3f3f; const int maxn = 1e5+5; const double eps = 1e-5; const double pi = asin(1.0)*2; const double e = 2.718281828459; int t; int n; int a[maxn], b[maxn]; int cnt; int main() { //fropen("in.txt", "r", stdin); scanf("%d", &t); while (t--) { map<int, int> mp; cnt = 0; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); } for (int i = 0; i < n; ++i) { scanf("%d", &b[i]); int temp = b[i] - a[i]; mp[temp]++; if (mp[temp] > cnt) { cnt = mp[temp]; } } printf("%d\n", cnt); } return 0; }