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$D1​,D2​,……,Dn​ , and the standard version of the song can be considered as another integer sequence $S_1,S_2,\dots \dots ,S_n$S1​,S2​,……,Sn​ . The score is the number of integers i satisfying $1\le i\le n$1≤i≤n and $S_i=D_i$Si​=Di​ .

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$1≤n≤105 ), indicating the length of the sequences D and S.

The second line contains n integers $D_1,D_2,\dots \dots ,D_n$D1​,D2​,……,Dn​ ( $-10^5\le D_i\le 10^5$−105≤Di​≤105 ), indicating the song performed by DreamGrid.

The third line contains n integers $S_1,S_2,\dots \dots ,S_n$S1​,S2​,……,Sn​ ( $-10^5\le S_i\le 10^5$−105≤Si​≤105 ), 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;
}