pku 3404 贪心的方法选择.txt

ACM资料大集合

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

//PKU 3404 贪心的方法选择
#define NMAX 55
#define INFI 99999
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back

bool cmp(int a,int b)
{
	return a<b;
}

int ti[NMAX];

void solve(int num)
{
	int ans=0,f1,f2,s1,s2,knum=num;//最快，次快，最慢，次慢
	sort(ti+1,ti+1+num,cmp);
	f1=1;f2=2;s1=num;s2=num-1;
	while(knum>=4)
	{	//每次借助快的人，让最满、次满过，有两种方法
		if(ti[f1]*2+ti[s1]+ti[s2]<ti[f1]+ti[f2]*2+ti[s1])//最快带最慢+最快回+最快带次慢+最快回更好
			ans+=ti[f1]*2+ti[s1]+ti[s2];
		else ans+=ti[f1]+ti[f2]*2+ti[s1];//最快跟次快一起过+最快回+最慢跟次慢一起过+次快回更好
		knum-=2;
		s1-=2;s2-=2;
//		printf("ans=%d\n",ans);
	}
	if(knum==3) ans+=ti[1]+ti[2]+ti[3];
    else if(knum==2) ans+=ti[2];
	else if(knum==1) ans+=ti[1];
	printf("%d\n",ans);	
}

int main()
{	int i,num;
	scanf("%d\n",&num);
	for(i=1;i<=num;i++) scanf("%d",&ti[i]);
	solve(num);
	return 0;
}