Tickets-白红宇

Tickets

阅读量：192 次

发布时间：2019-02-28

本文共 1465 字，大约阅读时间需要 4 分钟。

Joe需要尽早完成卖出所有电影票的任务。每位顾客可以单独买一张票或与旁边的顾客一起买两张票。目标是通过选择最优的购买方式，缩短总时间。

步骤解析：

定义状态：设f[i]为卖出前i张票所需的最短时间。

状态转移：

当第i张票单独买时，f[i] = f[i-1] + a[i]。

当第i-1和i两张票一起买时，f[i] = f[i-2] + b[i-1]。

取两种状态中的最小值。

初始化：

f[1] = a[1]（只能单独买）。

f[2] = min(f[1] + a[2], b[1])。

递推计算：从i=3到n，依次计算每个f[i]。

时间转换：总时间转换为HH:MM:SS格式，根据每日8:00:00 am计算完成时间。

代码实现：

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
#include 
       
        
#include 
        
          #include 
         
           #include 
          
            #include 
           
             using namespace std; #define N 10005 // 最大N设为10005以防止溢出 int main() { int t; // 测试用例数 cin >> t; while (t--) { int n; // 总人数 cin >> n; int a[N] = {0}; // 单独买一张的时间数组 int b[N] = {0}; // 买两张的时间数组 int f[N] = {0}; // 最短时间数组 for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i <= n - 1; ++i) { cin >> b[i]; } f[1] = a[1]; if (n >= 2) { f[2] = min(f[1] + a[2], b[1]); } for (int i = 3; i <= n; ++i) { f[i] = min(f[i-1] + a[i], f[i-2] + b[i-1]); } int total_time = f[n]; int h, m, s; h = (total_time / 3600) + 8; // 8点开始工作 total_time %= 3600; m = total_time / 60; s = total_time % 60; // 格式化输出时间 if (h < 10) { printf("0%d:", h); } else { printf("%d:", h); } if (m < 10) { printf("0%d:", m); } else { printf("%d:", m); } if (s < 10) { printf("0%d am\n", s); } else { printf("%d am\n", s); } } return 0; }