现在的位置: 首页 > 综合 > 正文

ZOJ – 1579(贪心)

2019年04月04日 ⁄ 综合 ⁄ 共 1993字 ⁄ 字号 评论关闭
A - Bridge

Time Limit:5000MS    Memory Limit:32768KB    64bit IO Format:%lld
& %llu

Description

A family of N people is passing a bridge at night. Since it is extremely dark, they walk with the help of a lamp. Unfortunitely the bridge is narrow, as a result a maximum of two people can cross at one time, and they must have the lamp
with them. Each person walks at a different speed, and a pair must walk together at the rate of the slower person. Now here is the problem: given the size of the family (N) and the time needed for each person to cross the bridge, try to figure out the minimum
total time that the family can cross the bridge.

Input

There are several test cases.

In each test case, there are 2 lines.

In the first line, an integer N will be given, which satisfies 0<=N<=100000. (Though a family of 100000 people is somewhat ridiculous.)

In the second line, N integers will be given, which are the time needed to cross the bridge for each person.

There are no extra line(s) between test cases.

Output

For each test case, output a line with one number, the minimum total time.

Sample Input

5
1 3 6 8 12

Sample Output

29

这个题目就是最后两个要借助前两个先过桥,有两种方案,比较选取最优即可,这样每次让最后两个过桥即可。这样总是最优的,因为与其晚会再过,不如现在过花时间短。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1111;
int a[maxn],n,res=0;
int handel(int n){
  if(n == 3){
     printf("%d %d\n",a[1],a[2]);
     printf("%d\n",a[1]);
     printf("%d %d\n",a[1],a[3]);
  }
  else if(n == 2){
    printf("%d %d\n",a[1],a[2]);
  }
  else {
    printf("%d\n",a[1]);
  }
}
void solve(){
  while(n>=4){
     int x = a[n-1];
     if(2*a[1]+x <= a[1] + 2*a[2]){
        printf("%d %d\n",a[1],a[n]);
        printf("%d\n",a[1]);
        printf("%d %d\n",a[1],a[n-1]);
        printf("%d\n",a[1]);
     }
     else{
        printf("%d %d\n",a[1],a[2]);
        printf("%d\n",a[1]);
        printf("%d %d\n",a[n-1],a[n]);
        printf("%d\n",a[2]);
     }
     n-=2;
  }
  handel(n);
}
void get_num(){
  int tn = n;
  while(tn>=4){
     int x = a[tn-1];
     if(2*a[1]+x <= a[1] + 2*a[2]){
        res+=2*a[1]+x+a[tn];
     }
     else{
       res+=a[1]+2*a[2]+a[tn];
     }
     tn-=2;
  }
  if(tn==3) res+= a[1]+a[2]+a[3];
  if(tn==2) res+=a[2];
  if(tn==1) res+=a[1];
}
int main()
{
   int T;
   scanf("%d",&T);
   while(T--){
     scanf("%d",&n);
     for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
     sort(a+1,a+1+n);
     res = 0;
     get_num();
     printf("%d\n",res);
     solve();
     if(T) printf("\n");
   }
   return 0;
}

抱歉!评论已关闭.