牛客网暑期ACM多校训练营（第五场）

J-plan（贪心）

题目描述

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.

输入例子:

4 2 3

输出例子:

-->

示例1

输入

4 2 3

输出

示例2

输入

5 1 3

输出

备注:

1<=n<=10^9
1<=p2,p3<=10^9
解题思路：题意很简单，就是安排n个学生全部住进2人间或者3人间（可以不住满）后使得总花费最少。典型的贪心策略，考虑性价比，设2人间的单价为x/间，性价比为x/2，3人间的单价为y/间，性价比为y/3，分为两种情况：一、如果3*x>2*y，表示应选3人间比较划算，那么有3种贪心可能：①n%3余数为0，全选3人间；②余数为1，全选3人间，或者最后1个学生选2人间，或者最后4个学生选2人间；③余数为2，全选3人间，或者最后2个学生选2人间；二、如果3*x<=2*y，表示选2人间比较划算，那么有2种贪心可能：①n%2余数为1，全选2人间，或者最后一个学生选3人间；②余数为0，全选2人间。
AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;LL n,x,y;

 int main(){

     while(cin>>n>>x>>y){

         if(*x>*y){

             if(!(n%))cout<<n/*y<<endl;

             else if(n%==)cout<<min(min((n/+)*y,n/*y+x),(n/-)*y+*x)<<endl;

             else cout<<min((n/+)*y,n/*y+x)<<endl;

         }

         else{

             if(n%)cout<<min((n/+)*x,(n/-)*x+y)<<endl;

             else cout<<n/*x<<endl;

         }

     }

     return ;

 }

巴特西