codeforces B. Vasya and Public Transport 解题报告

题目链接：http://codeforces.com/problemset/problem/355/B

题目意思：给出四种票种，c1: 某一部bus或者trolley的单程票（暗含只可以乘坐一次）；c2、c3、c4乘坐次数没有限制。c2：某一部bus或者trolley可以乘坐无限次；c3：所有的bus或者trolley可以乘坐无限次；c4：所有的bus和trolley可以乘坐无限次。根据给出的n buses 和m trolleys 每一辆的乘坐次数，找出最便宜的买票方式，输出要花费的金额。

对于每一部bus或者trolley，无非从c1或者c2选择。这里以选择某一个序号为 i 的bus的票为例。选择c2的条件是：（ai * c1） > c2（加多个“=”也可以），否则选择c1。为所有的bus买完票后（每一个选择都符合局部最优的，贪心的核心思想啊～～），统计这个和，再与c3比较，得到不考虑买c4这种票的情况下，对所有bus来说最好的买票和。（有可能买一张所有bus都可以乘坐无限次的票比这个和还要便宜的！）trolley的买票选择也类似。也得到一个撇开c4，对所有trolley来说的最好买票和。把这两个和相加，再与c4比较，哪个较小即是答案。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 #define max(x, y)  ((x) < (y) ? (x) : (y))     // 比较两个数的较小值

 const int maxn =  + ;

 int a[maxn], b[maxn];

 int main()

 {

     int c1, c2, c3, c4, n, m, i;

     while (scanf("%d%d%d%d", &c1, &c2, &c3, &c4) != EOF)

     {

         scanf("%d%d", &n, &m);

         for (i = ; i < n; i++)

             scanf("%d", &a[i]);         // buses

         for (i = ;  i< m; i++)

             scanf("%d", &b[i]);         // trolleys

         int sum1, sum2, max1, max2;

         sum1 = sum2 = ;

         for (i = ; i < n; i++)

         {

             if (a[i] * c1 <= c2)       // 买第一种票比第二种票便宜
                 sum1 += a[i] * c1;

             else

                 sum1 += c2;

         }

         for (i = ; i < m; i++)

         {

             if (b[i] * c1 <= c2)

                 sum2 += b[i] * c1;

             else

                 sum2 += c2;

         }

         max1 = max(sum1, c3);   // 组合了第一和第二种票的买票方式后，与买第三种票（所有bus乘坐次数无限制）作比较，求得较小值
         max2 = max(sum2, c3);

         max1 += max2;           // 在不考虑买第四种票的情况下buses和trolleys买票的最优值
         int maxsum = max(max1, c4);    // 有可能买所有的bus和trolley的无限制搭乘次数的票（c4）比之前求得的最优值还好
         printf("%d\n", maxsum);

     }

     return ;

 }

巴特西

codeforces B. Vasya and Public Transport 解题报告

最新文章

热门文章