周五那天,學長出了個題目,我就不粘貼題目了,簡述下題目的大致思路

Input

第一行給出一個整數n,第二行給定n個整數,第三行給定一個整數a,接下來a行表示挑選第二行中第幾個編號的數字

Output

輸出a行,每行輸出表示當每次挑選完一個數后剩余數的中位數的大小

我開始這道題是直接不斷快排暴力做的,不過提交的時候超時了,然后學長發了答案,不得不說,我該好好學數據結構了

#include<iostream> using namespace std; #include<string> #include<algorithm> #pragma warning (disable:4996) #include <climits> #include <vector> int book[1000000]; typedef struct a {int id;int x; }wangzi; wangzi wangzis[100000]; bool cmp(wangzi a, wangzi b); int main() {int n;cin >> n;for (int cnt = 1; cnt <= n; cnt++) {scanf("%d", &wangzis[cnt].x);wangzis[cnt].id = cnt;}sort(wangzis + 1, wangzis + n + 1, cmp);int t;cin >> t;int k = n;for (int cnt = 0; cnt < t; cnt++) {int id, sum = 0;int a, b;cin >> id;book[id] = 1;k--;for (int cnt1 = 1; cnt1 <= n; cnt1++) {if (!book[wangzis[cnt1].id]){sum++;if (k % 2 == 0) {if (sum == k / 2 + 1)a = wangzis[cnt1].x;if (sum == k / 2)b = wangzis[cnt1].x;}if (sum == k / 2 + 1) {if (k % 2 == 1) {printf("%d", wangzis[cnt1].x);}else {if ((a+b) / 2 * 2 == a+b) {printf("%d", (a + b) / 2);}else{printf("%.1f", (double)(a + b) / 2);}}putchar('\n');break;}}}}return 0; } bool cmp(wangzi a, wangzi b) {return a.x > b.x; }

總結

以上是生活随笔為你收集整理的周五测试题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。