（第五场）J plan 【贪心】

题目链接：https://www.nowcoder.com/acm/contest/143/J

题目描述

There are n students going to travel. And hotel has two types room:double room and triple room. The price of a double room is p2 and the price of a triple room is p3

Now you need to calulate the minimum total cost of these students.

输入描述:

The first line has three integers n, p2, p3

输出描述:

Output the minimum total cost.

示例1

输入

4 2 3

输出

示例2

输入

5 1 3

输出

备注:

1<=n<=10^9

1<=p2,p3<=10^9

题目大意：

n 个人出去玩，给定双人房和三人房的价格，求最少的住宿花费
1<=n<=10^9

官方题解：

脑补一下可以发现：最后答案一定是几乎全选性价比最高的那种房间
然后再加上几间其他的
所以二人间和三人间里数量用的最少的房间不会超过 3
枚举一下用了几间就好了

大概思路：

因为从全局来看我们要多选性价比高的房间，所以模拟一下分为两种大情况，而每种小情况的最后可能刚刚好住满，可能有剩余，如果双人房性价比高，那么最后有可能会剩下一个可怜的家伙，那时我们要考虑单个住便宜或是跟前面的合住三人房便宜了；如果三人房性价比高，那么最后可能剩下一个人，可能剩下两个人，综上所述，数量用的最少的房间不超过3.

AC code：

 #include <bits/stdc++.h>

 #define INF 0x3f3f3f3f

 #define ll long long int

 using namespace std;

 ll N, p2, p3, u;

 int main()

 {

     scanf("%lld%lld%lld", &N, &p2, &p3);

     double xj_1 = p2/2.0;

     double xj_2 = p3/3.0;

     long long int ans = ;

     if(xj_1 <= xj_2)

     {

         if(N%)

         {

             ans = (N/-)*p2 + min(p2*, p3);

         }

         else ans = (N/)*p2;

     }

     else

     {

         if(N% == )

         {

             ans = (N/-)*p3 + min(p2*, p3*);

         }

         else if(N% == )

         {

             ans = (N/-)*p3 + min(p2+p3, p3*);

         }

         else

         {

             ans = N/*p3;

         }

     }

     printf("%lld\n", ans);

     return ;

 }

巴特西