題目

要把即將到達港口的集裝箱放到船上，但集裝箱只能按順序到達港口，船也只能按順序停靠港口，也就是說放完第一個集裝箱才能放置下一個，第一艘船開走之后才能給第二艘船放集裝箱，現在給出集裝箱的數量n（1＜n＜100000）和船的數量s（1＜s≤n），下面的n行每行一個數（輸入順序就是集裝箱到達港口順序），表示每個集裝箱的重量，已知每艘船的載重都相等，船上集裝箱的重量不能超過載重，求船的最小載重，
輸入樣例
7 5
10
40
30
10
50
11
40
輸出樣例
50
樣例解釋
第一艘船裝（10，40），第二艘（30，10），第三艘（50），第四艘（11），第五艘（40），所以最小載重50

分析

采用二分法，按照題意我們進行順序裝箱，若在載重量為load下，s艘船能裝載n個給定重量的集裝箱，我們稱其為滿足題意的，易知載重量load越大，該性質就越滿足，而load越小，就越難以滿足該性質，因而我們求滿足該性質的邊界，也即最小的載重量load，
在check()中判別在load下，是否滿足性質，這里我們判斷裝完集裝箱后，所需船只數是否大于題中所給的數量s，
在主函式中，采用整數二分，二分的Left可任意取某個集裝箱的重量，Right取所有集裝箱的重量和，

代碼

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, s; //集裝箱和船
int load;
int q[N];//集裝箱重量
int ship[N];

bool check(int load, int n, int s){
	int k = 0;//當前船數 
	for(int i = 0; i < N; i ++ ) ship[i] = 0;//船的載重狀態 
	//裝載貨物
	for(int i = 0; i < n; i ++ ){
		if(q[i] > load) return false;
		else{
				if(ship[k] + q[i] <= load) ship[k] += q[i];
				else{
			 	  k += 1;
				  ship[k] = q[i]; 
				  }
			}
	}
	if(k >= s) return false;  //所需船只數是否大于船的數量s
	else
	 return true;
}

int main(){
	scanf("%d%d", &n, &s);
	for(int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
	
	int sum = 0;
	for(int i = 0; i < n; i ++ ) sum += q[i];
	
	int l = q[0], r = sum;
	while(l < r){
		int mid = l + r >> 1;
		if(check(mid, n, s)) r = mid;
		else l = mid + 1;
	}
	cout<<l<<endl;
//	cout<< check(500, n, s) <<endl;
//	cout<< n << " " << s <<endl;
//	for(int i = 0; i < n; i ++ ) printf("%d ", q[i]); 
	return 0;

}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/247730.html

標籤：其他

上一篇：C++炸彈小游戲

下一篇：C++學習筆記，堅持自律！