忍者ブログ
23 December

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

21 December

SRM600 div2 easy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12824

cnt[i]には地点iにおける、乗客の人数が入っている。
全ての乗客をX席あるバスを使って全員運びたい。
バスを派遣するコストが1台につきbaseCose + X * seatCostで与えられる時、
最小コストを求めよ。

制限:
1≦ i ≦ 50
1 ≦ cnt[i] ≦ 100
1 ≦ baseCost, seatCost ≦ 100

みたいな問題。


解法

ちょっと悩んだけど、数がそんなに多くないので
全部の場合についてのコストの合計を調べて、min取れば大丈夫そう。

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

class TheShuttles{
public:
	int getLeastCost(vector<int> cnt,int baseCost,int seatCost){
		int max_bus=0;
		
		for(int i=0;i<cnt.size();i++){
			if(i==0)max_bus = cnt[i];
			else max_bus = std::max(max_bus,cnt[i]);
		}
		int mc=0;
		
		for(int i=1;i<=max_bus;i++){
			int cost = 0;	
			for(int j=0; j<cnt.size(); j++){
				cost += (int)(1.*cnt[j]/i+0.99) * baseCost + i * seatCost * (int)(1.*cnt[j]/i+0.99);
			}
			if(i==1) mc = cost;
			else mc = std::min(mc,cost);
		}
		return mc;
	}
};

PR