【STL/思维】King of Karaoke

题意:

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 , and the standard version of the song can be considered as another integer sequence . The score is the number of integers satisfying and .

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 (about 100), indicating the number of test cases. For each test case:

The first line contains one integer (), indicating the length of the sequences and .

The second line contains integers (), indicating the song performed by DreamGrid.

The third line contains integers (), indicating the standard version of the song.

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

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
Hint
For the first sample test case, DreamGrid can choose and changes to .

For the second sample test case, no matter which DreamGrid chooses, he can only get at most 1 match.

分析:给两个数组,作差求差的众数。该众数可以与题干上说的那个magic数字进行调整,即为得分,刚开始的思路是做桶,但是数组下标不能为负数,需要整体把负数域搬到正数轴上,所以干脆利用map<int,int>偷懒。

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
int arr[100000];
//int bucket[1000000];
map<int, int> mapp;

int max(int x, int y) { return x >= y ? x : y; }
int main()
{
  int T;
  cin >> T;
  while (T--)
  {
    memset(arr, 0, sizeof(arr));
    mapp.clear();
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
      cin >> arr[i];
    }
    int temp = 0;
    for (int i = 0; i < n; i++)
    {
      cin >> temp;
      mapp[arr[i] - temp]++;
    }
    int maxx = -1;
    for (auto i : mapp)
    {
      maxx = max(i.second, maxx);
    }
    cout << maxx << endl;
  }
  return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

20 − 19 =