POJ 5253 Fence Repair

2019-11-08 00:54:16

字体：大中小

来源：转载

供稿：网友

原题链接

思路：倒着想，木块已经全部切割，每次选择最小的两块合并，直到合并为一块为止。

AC代码：

#include <iostream>#include <algorithm>#include <stdlib.h>using namespace std;int l[20001];int n;int main(){ int i,j,min0,min1; long long money=0; cin>>n; for(i=0;i<n;i++){ cin>>l[i]; } while(n>1){ min0=0,min1=1; if(l[min0]>l[min1]) swap(min0,min1); for(j=2;j<n;j++){ if(l[j]<l[min0]){ min1=min0; min0=j; } else if(l[j]<l[min1]){ min1=j; } } int t=l[min0]+l[min1]; money+=t; if(min0==n-1) swap(min0,min1); l[min0]=t; l[min1]=l[n-1]; n--; } cout<<money<<endl; return 0;}

也可以用PRiority_queue，省去找最小木块和次小木块的步骤。

AC代码：

#include <iostream>#include <stdio.h> #include <algorithm>#include <cstdlib>#include <queue> #include <vector>#include <functional> //greater<int>using namespace std;priority_queue<int, vector<int>, greater<int> > l;int n;int main(){ int i,j,t; long long money=0; cin>>n; getchar(); for(i=0;i<n;i++){ cin>>t; getchar(); l.push(t); } while(1){ int min0=l.top(); l.pop(); int min1=l.top(); l.pop(); t=min0+min1; money+=t; if(l.empty()) break; l.push(t); } cout<<money<<endl; return 0;}

上一篇：SPOJ-TTM - To the moon(主席树,经典)

下一篇：geotools中的空间关系（Geometry Relationships）和空间操作（Geometry Operations）