浙江科技学院第十三届程序设计竞赛 1008-A Heavy Rainy Day【贪心思维】

红太狼 2022-07-28 01:26 87阅读 0赞

# A Heavy Rainy Day #

##### Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other) #####

##### Total Submission(s) : 476 Accepted Submission(s) : 124 #####

#### Font: Times New Roman | Verdana | Georgia ####

#### Font Size: ← → ####

### Problem Description ###

As you know, Hangzhou always rains heavily, especially in Xiaoheshan area, which does annoy ACMers for a longer time. One day, N hardworking ACMers were playing League of Legends in the lab, of course not include me, while it was raining cats and dogs. Everyone wanted to come back to the department where they were living together, but no one wanted to be soaked without umbrella. Unfortunately, they only had one umbrella, which is too small to take more than two individuals. The time that everyone needs to spent to go to the department is known. If two guys came back together, it will take the longer time of this two guys. The question is the earliest time they come back to the department.

### Input ###

The first line contains an integer T(1<=T<=20),which is the number of test cases.  
For each testcase:  
The first line contains one integer N ,1<=N<=1000, present N ACMers want to come back,  
The second line contains N integers Si, present the time the ith ACMers need.

### Output ###

The shortest time they need to come to the department.

### Sample Input ###

1
    4
    1 2 5 10

### Sample Output ###

### Author ###

bytelin

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int map[10000];
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            int n;
            scanf("%d",&n);
            int i,j;
            for(i=0;i<n;i++)
            {
                scanf("%d",&map[i]);
            }
            int ans=0;
            sort(map,map+n);
            while(n>=4)
            {
                if((map[0]*2+map[n-1]+map[n-2])>(map[0]+map[1]*2+map[n-1]))
                {
                    ans+=map[0]+map[1]*2+map[n-1];
                }
                else
                {
                    ans+=map[0]*2+map[n-1]+map[n-2];
                }
                n-=2;
            }
            if(n==3)
            {
                ans+=map[0]+map[1]+map[2];
            }
            else if(n==2)
            {
                ans+=map[1];
            }
            else
            ans+=map[0];
            printf("%d\n",ans);
        }
        return 0;
    }