c904 - 天龍國的蜜蘋果

🔗 前往 ZeroJudge 原題

題目描述

題目要求從 N 個蘋果中，針對 M 個不同的 K 值，每次選出 K 個蘋果，使得選出的蘋果的單位重量售價（售價總和除以重量總和）最大化，並輸出對應的 K 值下的最大單位重量售價，精確到小數點後兩位。

解題思路

本題的核心思想是利用二分搜尋來尋找最大單位重量售價。對於每個 K 值，我們定義一個函數來計算給定單位重量售價下，可以選取的蘋果數量。然後，我們在可能的單位重量售價範圍內（從 0 到所有蘋果的最大售價）進行二分搜尋，直到找到滿足條件的最大單位重量售價。

具體步驟如下：

1. 對於每個 K 值，定義一個二分搜尋函數 bs(min, max, k, n)。
2. 在二分搜尋中，計算一個中間值 m，代表假設的單位重量售價。
3. 對於每個蘋果，計算其在單位重量售價為 m 時的“價值”：b[i] = a[i][1] - m * a[i][0]。
4. 將所有蘋果的“價值”排序。
5. 選擇價值最高的 K 個蘋果，計算其總價值。
6. 如果總價值大於等於 0，則說明 m 可能過小，將搜尋範圍調整到 [m, max]。
7. 否則，說明 m 過大，將搜尋範圍調整到 [min, m]。
8. 重複步驟 2-7，直到找到滿足條件的最大單位重量售價。

複雜度分析

• 時間複雜度: O(M * N * log(N) * log(max_v))，其中 M 是 K 值的數量，N 是蘋果的數量，log(N) 是排序的複雜度，log(max_v) 是二分搜尋的複雜度，max_v 是蘋果的最大售價。
• 空間複雜度: O(N)，主要用於儲存蘋果的重量和售價以及計算中間價值的 b 陣列。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
double a[1000][2]={0},b[1000]={0};
double bs(double min,double max,int k,int n){
	double m=(max+min)/2,sum=0;
	if(max<min)
		return m;	
	for(int i=0;i<n;i++)
		b[i]=a[i][1]-m*a[i][0];
	sort(b,b+n);
	for(int i=0;i<k;i++)
		sum+=b[n-i-1];
	if(sum>=0)
		return bs(m,max-0.0001,k,n);
	return bs(min+0.0001,m,k,n);		
}
int main(){
	int N,M,K;
	double max=0;
	cin >> N >> M;
	for(int i=0;i<N;i++){
		cin >> a[i][0] >> a[i][1];
		max+=a[i][1];
	}
	for(int i=0;i<M;i++){
		cin >> K;
		printf("%.2f\n",bs(0,max,K,N));
	}
}