題目描述

公司組織了一次考試,現在考試結果出來了，想看一下有沒人存在作弊行為,但是員工太多了,需要先對員工進行一次過濾,再進一步確定是否存在作弊行為。

過濾的規則為:找到分差最小的員工ID對(p1,p2)列表,要求p1<p2

員工個數取值范國:O<n<100000

員工ID為整數,取值范圍:0<=n<=100000

考試成績為整數,取值范圍:0<=score<=300

輸入描述

員工的ID及考試分數

輸出描述

分差最小的員工ID對(p1,p2)列表,要求p1<p2。每一行代表一個集合,每個集合內的員工ID按順序排列,多行結果也以員工對中p1值大小升序排列(如果p1相同則p2升序)。

樣例1

輸入：

5
1 90
2 91
3 95
4 96
5 100

輸出:

1 2
3 4

解釋:

輸入：第一行為員工個數n，后續的n行第一個數值為員工ID,第二個數值為員工考試分數

輸出:員工1和員工2的分差為1,員工3和員工4的分差也為1,因此最終結果為

1 2
3 4

樣例2

輸入：

5
1 90
2 91
3 92
4 85
5 86

輸出：

1 2
2 3
4 5 

代碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100000
// 定義結構體，用于存儲員工的ID和分數
typedef struct {int id;int score;
} pairs;
// 定義比較函數，用于qsort函數對員工按照id進行排序
int cmp(const void *a, const void *b) {int id1 = ((pairs *)a)->id;int id2 = ((pairs *)b)->id;return id1 - id2;
}
int main() {int n;scanf("%d", &n);// 創建一個動態數組用于存儲員工的ID和分數pairs *p = (pairs *)malloc(n * sizeof(pairs));for (int i = 0; i < n; i++) {scanf("%d %d", &p[i].id, &p[i].score);}int min = 300;for (int i = 0; i < n - 1; i++) {min = abs(p[i + 1].score - p[i].score) < min? abs(p[i + 1].score - p[i].score): min;}// 創建一個動態數組用于存儲分差最小的員工ID對pairs *res = (pairs *)malloc(n * sizeof(pairs));int count = 0;for (int i = 0; i < n - 1; i++) {// 如果當前分差等于最小分差，則將當前員工ID對添加到結果動態數組中if (abs(p[i + 1].score - p[i].score) == min) {res[count].id = p[i].id;res[count].score = p[i].score;count++;}}qsort(res, count, sizeof(pairs), cmp);// 遍歷排序后的員工動態數組，計算相鄰員工的分差for (int i = 0; i < count; i++) {printf("%d %d\n", res[i].id, res[i].id + 1);}return 0;
}