這就是…

題目描述

在麥克雷的面前有N個數，以及一個R*C的矩陣。現在他的任務是從N個數中取出 R*C 個，并填入這個矩陣中。矩陣每一行的法值為本行最大值與最小值的差，而整個矩陣的法值為每一行的法值的最大值。現在，麥克雷想知道矩陣的最小法值是多少。

輸入

輸入共兩行。

第一行是三個整數：n，r，c。（r, c <= 104, r * c <= n <= 106）

第二行是 n 個整數 Pi。(0 < pi <= 109)

輸出

輸出一個整數，即滿足條件的最小的法值。

樣例輸入

7 2 3
170 205 225 190 260 225 160

樣例輸出

30

思路

給定一個N如果可以找到R個C滿足法值小于等于N，那么N就符合答案。于是就用二分查找，一步步逼近最小的N。

AC代碼

#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #define N 1000006 using namespace std; int n, r, c; int a[N], dis[N]; int solve(int t) {int i = c; int sum = 0; //sum表示能找到C的個數 while(i <= n) {if(dis[i] <= t) {sum++;i += c; //找到一個C，從下一個i + c 開始找 if(sum >= r) { //如果能找到R個C就返回true return 1;}}else {i++;}}return 0; } int main() { // freopen("in.txt", "r", stdin);while(scanf("%d%d%d", &n, &r, &c) != EOF) {for(int i = 1; i <= n; i++) {scanf("%d", &a[i]);}sort (a + 1, a + 1 + n);for(int i = c; i <= n; i++) { //dis[]記錄每C個的法值 dis[i] = a[i] - a[i - c + 1];}int left = 0, right = 1e9; //二分找答案 while(left < right) {int mid = (left + right) / 2;int t = solve(mid);if(t) {right = mid; }else {left = mid + 1; } // printf("%d %d\n", left, right); }printf("%d\n", left);}return 0; }

總結

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

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