计蒜客手机零件采购（简单背包）

我不是女神ヾ 2024-02-18 16:30 37阅读 0赞

手机组装是一个非常难以获得收益的行业，因此零件提供商的选择就变得非常重要。请帮助法师康公司以尽可能最廉价的方式取得他们组装桔子手机所需的零件。法师康公司从一些零件生产商那购买零件（假定不区分零件种类），每个零件生产商卖给法师康公司零件的价格不一定相同。已知零件生产商可以卖给法师康公司的零件数就是有限的了，每天,法师康公司从每个零件生产商那购买一定量的零件，少于或等于该生产商所能提供的最大值。给出法师康公司的每日的零件需求量，连同每个零件生产商可提供的零件每件的价格,请计算法师康公司所要付出钱的最小值。

注意:每天零件生产商的零件的总数对法师康公司来说是足够的

输入第1行包括两个数值：法师康公司需要的零件的总数N（0≤N≤2000000）和零件生产商的数量M（0≤M≤5000）。

第2行至第M+1行中，每行包括两个整数，分别表示一个零件生产商提供的一个零件的价格X（0≤X≤1000）和零件生产商一天能提供的零件总量Y（0≤Y≤2000000）。

输出包括一行，表示法师康公司得到生产所需零件需要的最小费用。

##### 样例输入 #####

100 5
    5 20
    9 40
    3 10
    8 80
    6 30

##### 样例输出 #####

630

AC代码：

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 5e3+10;
    struct node{
    	int price ;
    	int num ;
    } home[maxn];
    
    bool cmp(const node& n1,const node&n2 ){
    		return n1.price < n2.price; 
    	}
    int main(){
    	int n,m;
    	while(scanf("%d%d",&n,&m)==2){
    		for(int i = 0; i < m; i++){
    			scanf("%d%d",&home[i].price,&home[i].num);
    		}
    		sort(home,home+m,cmp);
    		
    		int totalPrice = 0;
    		for(int i = 0; i < m; i++){
    			if(n >= home[i].num){
    				totalPrice += home[i].num*home[i].price;
    				n -= home[i].num;
    			}else {
    				totalPrice += n*home[i].price;
    				break;
    			}
    		}
    		printf("%d\n",totalPrice);
    	}
    	return 0;
    }