“日拱一卒，功不唐捐”

写在前面

本人因为没开long long而被迫参考楼下思路重构代码，最后发现这个问题加了long long才得以AC

进入正题

-->这是题面

这是百度翻译

题面大家应该很清晰了，

这个水题（我也就交了七遍）的主要做法是模拟+一点贪心+小学二年级数学

我们不难想到，把价值高的放在最后摧毁会更优

直接上一个sort

但是，问题来了：

1、可能将这一类物品摧毁一部分后，就直接进入下一阶段

2、可能将这一类物品全部摧毁后，还不能满足下一阶段

3、可能将这一类物品全部摧毁后，会横跨好几个阶段

4、可能到达最后一个阶段，还有许多物品没有被摧毁

其实让我们用代码直接模拟这个过程即可

如果遇到我们上述问题，多特判几下

具体解释在下面代码中

注：变量名zsf，lkp，lzx都是我的学姐长，（显然，lkp没用（到））

 1 /*

 2 Work by: Suzt_ilymtics

 3 */

 4 #include<iostream>

 5 #include<cstdio>

 6 #include<algorithm>

 7 using namespace std;

 8 struct node{

 9     long long num , c;

10     bool operator < (const node & b) const {return c < b.c; }

11 }a[110];

12 int n,t,zsf = 1;//zsf贡献因子

13 long long p[110], lzx = 0, wz = 1;//lkp摧毁物品数，lzx与下一个阶段的差距

14 long long ans = 0;

15 int max(int x,int y){return x > y ? x : y ;}

16 int main()

17 {

18     scanf("%d",&n);

19     for(int i=1;i<=n;++i) scanf("%d%d",&a[i].num,&a[i].c);

20     scanf("%d",&t);

21     for(int i=1;i<=t;++i) scanf("%lld",&p[i]);

22     sort(a+1,a+1+n);

23     int i = 1;

24     lzx = p[zsf];//算一下差距

25     while(i<=n){

26         if(a[i].num >= 0 && a[i].num - lzx < 0){//如果当前物品数不够

27             ans += a[i].c * zsf * a[i].num;//先加上当前价值*贡献因子*剩余的数量

28             lzx -= a[i].num;//差距要减掉a[i].num

29             a[i].num = 0;//减完之后还剩0个

30             i++; //换下一个物品

31          }

32         else{//如果够

33             ans += a[i].c * zsf * lzx;//直接加上当前价值*贡献因子*差距的数量

34             a[i].num -= lzx;//当前物品的数量要减去差距

35             if(zsf > t) {

36                 lzx = max(a[i].num,1);

37                 continue;//如果 贡献因子超过第t个数，则贡献因子达到最大值

38             }

39             zsf++;//贡献因子++

40             if(zsf > t) continue;

41             lzx = p[zsf] - p[zsf-1];//更新差距

42         }

43     }

44     printf("%lld",ans);

45     return 0;

46 }

为了卡我自己的而手造的样例：

//cin:

1

5 1

2

2 3

//cout:

//10

The end

如果您有什么疑问的地方，尽管来骚扰我

巴特西

CF175C Geometry Horse 题解

“日拱一卒，功不唐捐”

写在前面

具体解释在下面代码中

为了卡我自己的而手造的样例：

The end

最新文章

热门文章