題意：
? ? ?有n個服務(wù)器，每個服務(wù)器都要安裝網(wǎng)線（必須也只能安裝一個），然后每個服務(wù)器都有mi種選擇網(wǎng)線的方式，每種方式兩個參數(shù)，一個是速度b,另一個是價錢p,然后讓你找到一個最大的比值 minb/sump,就是所有的選擇中最小的那個速度，必上話的錢的總和。


思路：?
? ? ? 這個題目按照討論組里面的說法估計做法很多，不管了，說下我自己的做法吧，我的做法有點像操作系統(tǒng)里面那個多路歸并（如果沒記錯是叫這個，做題的時候突然想到這個方式，試了下，還真行），具體是這樣，枚舉最小的b，也就是最小的那個帶寬，對于每個服務(wù)器，我們可以先把他所有的可選擇項都按照帶寬從小到大排序，排序后再倒著預(yù)處理得到每個選項后面中最小的那個花費，全部這樣處理完之后就得到了一個二維的表，然后我們開始枚舉，每個表都是根據(jù)帶寬從小到大排序的，這樣所有中最小的那個肯定就是某一個的第一項，我們O(n)的時間找到第一項，以這一項的帶寬為最小帶寬，花費是當(dāng)前這個選項的花費，其他的就選最小的花費，然后刪除找到的這一項，就這樣一直找到頭一個服務(wù)器的選項全都用完了位置，還有就是刪除項的時候可以開一個一維數(shù)組，記錄當(dāng)前這個服務(wù)器已經(jīng)用到第幾項了，刪除第i個服務(wù)器的當(dāng)前項，直接mk[i]++就行了，16msAC,總的時間復(fù)雜度最壞應(yīng)該是 O(n*n*n) 1000000吧。感覺思路有點瞎扯了，呵呵，題目不難，瞎扯就瞎扯吧，好就說這些。


#include<stdio.h>
#include<string.h>
#include<algorithm>


#define N 100 + 10
#define INF 1000000000


using namespace std;


typedef struct
{
? ? int b ,p ,minp;
}NODE;


NODE node[N][N];
int now[N] ,num[N];


bool camp(NODE a ,NODE b)
{
? ? return a.b < b.b;
}


int main ()
{
? ? int t ,i ,j ,n ,tmp ,sn;
? ? scanf("%d" ,&t);
? ? while(t--)
? ? {
? ? ? ? scanf("%d" ,&n);
? ? ? ? for(i = 1 ,sn = 0 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d" ,&num[i]);
? ? ? ? ? ? sn += num[i];
? ? ? ? ? ? for(j = 1 ;j <= num[i] ;j ++)
? ? ? ? ? ? scanf("%d %d" ,&node[i][j].b ,&node[i][j].p);
? ? ? ? ? ? sort(node[i] + 1 ,node[i] + num[i] + 1 ,camp);
? ? ? ? ? ? for(j = num[i] ;j >= 1 ;j --)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(j == num[i] || tmp > node[i][j].p)
? ? ? ? ? ? ? ? tmp = node[i][j].p;
? ? ? ? ? ? ? ? node[i][j].minp = tmp;
? ? ? ? ? ? }
? ? ? ? ? ? now[i] = 1;
? ? ? ? }
? ? ? ? double Ans = 0;
? ? ? ? int nowb ,nowp;
? ? ? ? while(sn--)
? ? ? ? {
? ? ? ? ? ? nowb = INF;
? ? ? ? ? ? nowp = 0;
? ? ? ? ? ? int mkbreak = 0;
? ? ? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(now[i] > num[i]) mkbreak = 1;
? ? ? ? ? ? ? ? if(nowb > node[i][now[i]].b)
? ? ? ? ? ? ? ? nowb = node[i][now[i]].b;
? ? ? ? ? ? }
? ? ? ? ? ? if(mkbreak) break;
? ? ? ? ? ? int mk = 0;
? ? ? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? //if(now[i] > num[i]) continue;
? ? ? ? ? ? ? ? if(!mk && nowb == node[i][now[i]].b)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? mk = 1;
? ? ? ? ? ? ? ? ? ? nowp += node[i][now[i]].p;
? ? ? ? ? ? ? ? ? ? now[i] ++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else nowp += node[i][now[i]].minp;
? ? ? ? ? ? }
? ? ? ? ? ? if(Ans < nowb * 1.0 / nowp)
? ? ? ? ? ? Ans = nowb * 1.0 / nowp;
? ? ? ? }
? ? ? ? printf("%.3lf\n" ,Ans);
? ? }
? ? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的POJ1018贪心（多路归并的想法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。