题意:将一根长为l的木棍锯成n段,使l1+l2+l3+....= l, 且每次锯木棍所需花费等于木棍长度。求最小花费。
题解:学习优先级队列。
#include <queue> #include <vector> #include <iostream> using namespace std; struct cmp { bool operator () ( const int &a, const int &b ) { return a > b ; } }; int main() { int n; __int64 ans = 0, first, second, temp; priority_queue<int,vector<int>,cmp> Q; scanf("%d",&n); for ( int i = 0; i < n; ++i ) { scanf("%d",&temp); Q.push ( temp ); } while ( Q.size () != 1 ) { first = Q.top (); Q.pop (); second = Q.top(); Q.pop (); temp = first + second; Q.push ( temp ); ans += temp; } printf("%I64d\n",ans); return 0; }
#include <queue> #include <iostream> using namespace std; struct node { __int64 value; bool operator < ( const node &a ) const { return value > a.value; } } temp; // 将temp定义在main函数里为什么就是错的呢? int main() { int n; node first, second; priority_queue<node> Q; scanf("%d",&n); for ( int i = 0; i < n; ++i ) { scanf("%d",&temp.value); Q.push ( temp ); printf("%I64d ", Q.top().value); } __int64 ans = 0; while ( Q.size () != 1 ) { first = Q.top(); Q.pop (); second = Q.top(); Q.pop (); temp.value = first.value + second.value; Q.push ( temp ); ans += temp.value; } printf("%I64d\n",ans); return 0; }
#include <cstdlib> #include <iostream> using namespace std; int array[20005], n; int cmp ( const void *a, const void *b ) { return *((int*)a) - *((int*)b); } void in ( int num, int start ) { int i = start; while ( i < n && array[i] < x ) { array[i-1] = array[i]; ++i; } array[i-1] = x; } int main() { int temp, i; scanf("%d",&n); for ( i = 0; i < n; ++i ) scanf("%d", array+i); qsort(array,n,sizeof(int),cmp); __int64 ans = 0; i = 0; while ( i < n-1 ) //当数组只剩下一个元素时则跳出。(因为该值在上一次循环时已经用到) { temp = array[i] + array[i+1]; in ( temp, i+2 ) //每次扔掉数组的前两个元素,并将temp的值按排序规律插到特定位置 ans += temp; ++i; } printf("%I64d\n",ans); return 0; }