jzoj3012. 【NOIP2012模拟10.6】购买

本文主要是介绍jzoj3012. 【NOIP2012模拟10.6】购买，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

Description

小N 最近迷上了购物每天都让小A 和小T 陪她逛街拿东西。最近商店出了这样的一个

活动:买东西送积分，就是买一件物品，送当前物品的积分ci*当前的倍率，初始倍率是1；

当倍率是i 的时候，如果你买的物品等于ti 个，那么倍率将加1.最多积分的人可以得到超限

量版的圆神手办。小N 十分喜欢这个手办但是她又有自己的购物计划，于是她想在这个计

划下尽量提高自己的积分。她有n 种东西要买，其中第i 种物品她要买ki 个，每个可以得到

ci 的积分。请告诉她积分最多能得到多少吧。

Input

第一行有一个整数n表示要买的种类。

接下来n行每行2个整数ki,ci表示数量和积分

接下来一行有一个正整数t表示奖励的倍数

接下来一行有t个递增的整数ti表示买了ti个物品之后以后买的物品得到的积分倍率将是(i+1)

Output

一个整数，表示小N能得到的最多积分

Sample Input

1
5 3
2
3 6

Sample Output

21

Hint

前3个物品得到的积分是331=9，后面2个物品的积分是322=12

60%的数据n<=10，sigma(ki)<=1000000

100%的数据n<=100,t<=100,ki<=10⁹,0<=ci<=1000,ti<=10¹²

分析

开始以为是什么高深的算法，自己也不会，就随便打了个暴模，想不到AC了。
题意其实就是把物品按积分由小到大排序，然后依次按照倍率增加要求的物品数改变乘的倍率。

CODE

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;struct llx{long long k,c;
}a[110];int n,m;
long long ans,tot,t[110];bool cmp(llx x,llx y){return x.c<y.c;
}int main(){scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%lld%lld",&a[i].k,&a[i].c);sort(a+1,a+n+1,cmp);scanf("%d",&m);for (int i=1;i<=m;i++)scanf("%lld",&t[i]);int i=0,k=1;while (i<n){i++;if (k==m+1) {while (i<=n){ans+=a[i].k*a[i].c*k;i++;}}if (tot+a[i].k<t[k]){ans+=a[i].c*a[i].k*k;tot+=a[i].k;}else{ans+=(t[k]-tot)*a[i].c*k;a[i].k=a[i].k-t[k]+tot;tot=t[k];k++;i--;}}printf("%lld\n",ans);return 0;
}

这篇关于jzoj3012. 【NOIP2012模拟10.6】购买的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---