http://poj.org/problem?id=1700
贪心问题
对于一个安排,怎么样是最小的?首先关于花费,对于每次运输,以最节约的方式运输。两种情况,一种最轻的作为往返,另外 一种是每次带一个,每次带一个。
就要进行选择。到最后特殊判断即可。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; ll n,x; const ll N=1e7+520; ll a[N],t; int main() { scanf("%lld",&t); while(t--) { x=0; scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); sort(a+1,a+1+n); ll k=1; while(n>3) { x+=min(2*a[1]+a[n-1]+a[n],2*a[2]+a[n]+a[1]); n-=2; } if(n==3) { x+=(a[1]+a[2]+a[3]); } if(n==2) { x+=a[2]; } if(n==1) { x+=a[1]; } cout<<x<<‘\n‘; } return 0; }