pc端测试webservice
浏览数：65 /
时间：2015年06月09日
题目的算法就是每次选择水果排序后，每次选择重量最小的两堆合并
#include<iostream>
#include<vector>
#include<iterator>
#include<set>
using namespace std;
int main()
{
int N;
cin>>N;
while(N--)
{
int num;
cin>>num;
multiset<long long>Apple;
while(num--)
{ long long weight;
cin>>weight;
Apple.insert(weight);
}
multiset<int>::iterator it;
long long temp1,temp2,result=0;
while(Apple.size()!=1)
{
temp1=*Apple.begin(); //set 是自动由小到大排序所以只要取出第一第二个即可
Apple.erase(Apple.begin());
temp2=*Apple.begin();
Apple.erase(Apple.begin());
result+=temp1+temp2;
Apple.insert(temp1+temp2);
}
cout<<result<<endl;
}
}注：不要使用algorithm头文件中的sort排序，因为这个在ACM平台上回超时，同时最好也别使用multiset.erase(first, last )貌似这个也会超时。。。很蛋疼。
最好请大神帮我分析一下set得数据结构，以及自带排序得实现和时间复杂度，因为sort是nlogn
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
