[NOIP 2016 普及组] 买铅笔

知识点

向上取整、枚举、整数运算

解题思路

对三种包装分别购买足够多的整包，包数为(n+s-1)/s；计算三种总价后取最小值。

正确性说明

同一种包装单价为正，购买恰好达到数量要求的最少包数一定最便宜。题意要求只选一种包装，因此枚举三种即覆盖所有合法方案。

易错点

不能混用不同包装；n能整除s时不能额外多买一包；乘法用long long。

复杂度

时间O(1)，空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,ans=LLONG_MAX;cin>>n;
    for(int i=0;i<3;++i){long long s,p;cin>>s>>p;ans=min(ans,(n+s-1)/s*p);}
    cout<<ans<<'\n';
}