当前位置: 首页 > 工具软件 > River Trail > 使用案例 >

1232:Crossing River(贪心)

萧胜
2023-12-01

【题目描述】
几个人过河,每次过两人一人回,速度由慢者决定,问过河所需最短时间。

【输入】
输入t组数据,每组数据第1行输入n,第2行输入n个数,表示每个人过河的时间。

【输出】
输出t行数据,每行1个数,表示每组过河最少时间。

【输入样例】
1
4
1 2 5 10
【输出样例】
17
题目分析:
这种过河问题求最少时间就本着能者多劳的原则去想就行。从一个人过河开始想,想到n个人就结束了。而这个题恰好也是这样。有以下四种情况:
我们用数组a来储存这n个人的过河时间,然后从小到大排序。
人数少于四个时很容易想,当人数大于四时有两种方案。
我们用a b c d来代替四个人。
方案一:a和b过河a回来,c和d过河,b回来,最后a和b过河。时间:a+2b+d.
方案二:a和c过去,a回来,a和d过去,a回来。最后a和b过去。时间:2
a+c+d

人数n过河最短时间
n=1a[1]
n=2min(a[1],a[2])
n=3a[1]+a[2]+a[3]
n>4a[1]+2a[2]+a[n]. 或者 2a[1]+a[3]+a[4]

n>=4是就要比较那种方案时间少了,然后就有点递推的意味了,运一次少两个人,运到最后就可以用n<4时的结论来直接得出结果。
代码:

#include<iostream>
#include<algorithm>
using namespace std;
int a[10001];
int coss(int);
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1);
        cout<<coss(n)<<endl;
    }
    return 0;
}
int coss(int n)
{
    int t1,t2;
    if(n==1) return a[1];
    else if(n==2) return a[2];
    else if(n==3) return a[1]+a[2]+a[3];
    else
    {
        t1=2*a[1]+a[n-1]+a[n];
        t2=a[1]+2*a[2]+a[n];
        return min(t1,t2)+coss(n-2);//t1和t2中最小值
    }
}
 类似资料: