1083 是否存在相等的差(20) - PAT乙级

发表于

1083 是否存在相等的差（20 point(s)）

给定 N 张卡片，正面分别写上 1、2、……、N，然后全部翻面，洗牌，在背面分别写上 1、2、……、N。将每张牌的正反两面数字相减（大减小），得到 N 个非负差值，其中是否存在相等的差？

输入格式：

输入第一行给出一个正整数 N（2 ≤ N ≤ 10 000），随后一行给出 1 到 N 的一个洗牌后的排列，第 i 个数表示正面写了 i 的那张卡片背面的数字。

输出格式：

按照“差值 重复次数”的格式从大到小输出重复的差值及其重复的次数，每行输出一个结果。

输入样例：

8
3 5 8 6 2 1 4 7

输出样例：

5 2
3 3
2 2

Solution

差值作为散列地址, f(key) = key, 在不同差值地址上计数, 对重复的差值进行排序

坑点:

  • 1, 牌从1开始计数, 1 2 3 4 5 ..
  • 2, 要对差值进行排序, 这里用了vector, 写cmp函数的方法, 不知道还有没有其他.
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 10000
typedef struct {
  int delta;
  int cnt;
} Node;

int cnt[MAXN];
vector<Node> ans;

int cmp(Node n1, Node n2) {
  return  n1.delta > n2.delta;
}

int main() {
  int N, v;
  cin >> N;
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < N; i++) {
    cin >> v;
    int d = (i < v) ? v-(i+1) : (i+1)-v;
    cnt[d]++;
  }

  for (int i = 0; i < MAXN; i++) {
    if (cnt[i] > 1) {
      Node node;
      node.delta = i; node.cnt = cnt[i];
      ans.push_back(node);
    }
  }

  sort(ans.begin(), ans.end(), cmp);
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i].delta << " " << ans[i].cnt << endl;
  }
  return 0;
}

Solution2:

第二遍做, 找出其他方法.

既然开了一个散列, 可以记录一个max作为遍历的头, 从max向下遍历。

坑点:

重复是出现次数大于1

#include <cstdio>
#include <cstring>
int cnt[10050];

int main() {
  int N; scanf("%d", &N);
  memset(cnt, 0, sizeof(cnt));
  int max = 0, back = 0, rst = 0;
  for (int i = 0; i < N; i++) {
    scanf("%d", &back);
    rst = (back > i+1) ? back - (i+1) : i+1 - back;
    cnt[rst]++;
    max = rst > max ? rst : max;
  }
  
  for (int i = max; i >= 0; i--) {
    if (cnt[i] > 1) {
      printf("%d %d\n", i, cnt[i]);
    }
  }
  return 0;
}