Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1941 Accepted Submission(s): 938
A good approach, reducing the total time of tickets selling, is let adjacent people buy tickets together. As the restriction of the Ticket Seller Machine, Joe can sell a single ticket or two adjacent tickets at a time.
Since you are the great JESUS, you know exactly how much time needed for every person to buy a single ticket or two tickets for him/her. Could you so kind to tell poor Joe at what time could he go back home as early as possible? If so, I guess Joe would full of appreciation for your help.
1) An integer K(1<=K<=2000) representing the total number of people;
2) K integer numbers(0s<=Si<=25s) representing the time consumed to buy a ticket for each person;
3) (K-1) integer numbers(0s<=Di<=50s) representing the time needed for two adjacent(相近的)people to buy two tickets together.
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define min(a, b) a<b?a:b 5 using namespace std; 6 int main() 7 { 8 int t; 9 int num1[2020], num2[2020], dp[2020]; 10 scanf("%d", &t); 11 while(t--) 12 { 13 int m; 14 scanf("%d", &m); 15 for(int i = 1; i <= m; i++) 16 scanf("%d", &num1[i]); 17 for(int i = 1; i <= m-1; i++) 18 scanf("%d", &num2[i]); 19 memset(dp, 0, sizeof(dp)); 20 dp[1] = num1[1]; 21 for(int i = 2; i <= m; i++) 22 dp[i] = min(dp[i-1] + num1[i], dp[i-2] + num2[i-1]); 23 int b, c, d; 24 b = dp[m] % 60; 25 c = dp[m] / 60 % 60; 26 d = dp[m] /3600; 27 d += 8; 28 char c1, c2; 29 if(d < 12) 30 { 31 c1 = 'a'; 32 c2 = 'm'; 33 } 34 else 35 { 36 d %= 12; 37 c1 = 'p'; 38 c2 = 'm'; 39 } 40 printf("%02d:%02d:%02d %c%c ", d, c, b, c1, c2); 41 } 42 return 0; 43 }