2020Dash-8

Final Dash

简单贪心

题目

传送门：购物娱乐

考察要点：贪心思想

有N种物品，每种初始价格是cost[i]，每种物品每被买走一个，价格上升up[i]，求买走m个物品的最小花费。

1<=n,m<=1000，1<=cost[i]，up[i]<=500 （水

做法

贪心。

策略：显然每次我们购买价格最小的物品，然后这个物品的价格就变成了｀nowcost[i]+up[i]｀，但是下次我们依然是买价格最小的物品，这样买M个就是最优的。

时间复杂度： O(N*M)

正确性证明

我们把N个物品拆成N*M个物品，相当于我们把买走一些物品以后的某个物品价格直接拿出来变成新物品。那么问题转化为：N*M个物品中买走M个，使总价格最小，那么问题就一目了然了。

代码

数据小，直接暴力。

const int N=1000000+1000; 
int n,m,a[N],ans=0;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m; int p=1;
	for(int i=1; i<=n; i++){
		int x,y; cin>>x>>y;
		for(int k=1; k<=m; k++){
			a[p]=x; x+=y; p++;
		}
	}
	sort(a+1,a+n*m+1);
	for(int i=1; i<=m; i++) ans+=a[i];
	return cout<<ans<<endl,0;
}

Plus

如果数据更大，那么就加入最小堆维护

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议