問題
http://community.topcoder.com/stat?c=problem_statement&pm=9933&rd=13506
複数のクレーンがあり、それぞれが運ぶことのできる最大の重さがわかっている。
また複数の積荷があり、これをすべて運びたい。
クレーンは同時に複数種類を動かすことができる。
このとき、すべての積荷を運ぶのに必要な最小時間を求める。
解き方
要素数は５０なので全探索可能。
vectorでeraseを使えばシンプルに実装できる。
コード
class ShipLoading {
public: int minimumTime(vector<int> cranes, vector<string> boxes) {
int n=cranes.size();
vector<int> box;
string str="";
FORE(i,0,boxes.size())str+=boxes[i];
stringstream out;
out<<str;
for(int num;out>>num;)box.push_back(num);
sort(cranes.rbegin(),cranes.rend());
sort(box.rbegin(),box.rend());
if(box.empty() || cranes[0]<box[0])return -1;
int ret=0;
while(!box.empty()){
ret++;
FORE(i,0,n)FORE(j,0,box.size()){
if(cranes[i]>=box[j]){
vector<int>:: iterator it=box.begin();
box.erase(it+j);
break;
}
}
}
return ret;
}
};
public: int minimumTime(vector<int> cranes, vector<string> boxes) {
int n=cranes.size();
vector<int> box;
string str="";
FORE(i,0,boxes.size())str+=boxes[i];
stringstream out;
out<<str;
for(int num;out>>num;)box.push_back(num);
sort(cranes.rbegin(),cranes.rend());
sort(box.rbegin(),box.rend());
if(box.empty() || cranes[0]<box[0])return -1;
int ret=0;
while(!box.empty()){
ret++;
FORE(i,0,n)FORE(j,0,box.size()){
if(cranes[i]>=box[j]){
vector<int>:: iterator it=box.begin();
box.erase(it+j);
break;
}
}
}
return ret;
}
};