250pt:
题意:提供每一件物品的重量item[i], 100<=item[i]<=300,一个容器只能最多承重300(inclusive),问最少要多少个容器
分析:贪心。除了三个都是100的能放在一个容器里,其他的最多两个。这样对100的个数(更确切的说是有多少组3个100)进行枚举讨论。注意,并不是有3个100就一定这三个放在一个容器里,比如100,100,100,180,180,180,更好的方案是100+180一组,所以要讨论3个100是否放一个容器的情况。 剩下的就是先排序,用两个指针从头和尾贪心遍历,如果头尾相加<300,那么这两个在同一个容器,不然尾单独一个容器,尾往前进一格。
代码:
int BinPacking::minBins(vector <int> item) { int cnt = 99999999; int zero = count(item.begin(),item.end(),100); for(int z=0;z<=zero/3;z++) { int sum = z; vector<int> temp; for(int i=0;i<item.size();i++) { if(item[i]!=100) temp.push_back(item[i]); } int zeroNumberIntoTemp = zero-z*3; while(zeroNumberIntoTemp--) temp.push_back(100); sort(temp.begin(),temp.end()); int i=0;int j = temp.size()-1; while(i<j) { if(temp[i]+temp[j]<=300) { sum++; i++; j--; } else { j--; sum++; } } if(i==j) sum++; cnt = min(sum,cnt); } return cnt; }
500pt和1000pt的暂时还不会,啥时会啥时填这个坑:)