我的PAT系列文章更新重心已移至Github悯恍,歡迎來(lái)看PAT題解的小伙伴請(qǐng)到Github Pages瀏覽最新內(nèi)容。此處文章目前已更新至與Github Pages同步。歡迎star我的repo。
題目
給定 N 張卡片只泼,正面分別寫上 1、2卵洗、……请唱、N,然后全部翻面过蹂,洗牌籍滴,在背面分別寫上 1、2榴啸、……、N晚岭。將每張牌的正反兩面數(shù)字相減(大減信赣 ),得到 N
個(gè)非負(fù)差值坦报,其中是否存在相等的差库说?
輸入格式:
輸入第一行給出一個(gè)正整數(shù) N(2 N
10 000),隨后一行給出 1 到 N 的一個(gè)洗牌后的排列片择,第 i 個(gè)數(shù)表示正面寫了 i
的那張卡片背面的數(shù)字潜的。
輸出格式:
按照“差值 重復(fù)次數(shù)”的格式從大到小輸出重復(fù)的差值及其重復(fù)的次數(shù),每行輸出一個(gè)結(jié)果字管。
輸入樣例:
8
3 5 8 6 2 1 4 7
輸出樣例:
5 2
3 3
2 2
思路
這個(gè)和之前一些記錄字符的題目相近啰挪,就是統(tǒng)計(jì)數(shù)字或者字符的出現(xiàn)次數(shù)或者其他相關(guān)信息。
數(shù)字出現(xiàn)的次序就是正面數(shù)字嘲叔,數(shù)字本身就是背面數(shù)字亡呵,兩者之差就是所需。
僅需注意兩小點(diǎn):
- 差值要取絕對(duì)值
- 輸出僅輸出出現(xiàn)次數(shù)大于等于2的
代碼
最新代碼@github硫戈,歡迎交流
#include <stdio.h>
int main()
{
int N, num, diff[10000] = {0};
scanf("%d", &N);
for(int i = 0; i < N; i++)
{ /* The front is i + 1, the back is num */
scanf("%d", &num);
diff[(num > i + 1) ? (num - i - 1) : (i + 1 - num)]++;
}
for(int i = N - 1; i >= 0; i--)
if(diff[i] >= 2)
printf("%d %d\n", i, diff[i]);
return 0;
}