客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
C. Fountains
time limit per test
2 secondsmemory limit per test
256 megabytesinput
standard inputoutput
standard outputArkady plays Gardenscapes a lot. Arkady wants to build two new fountains. There are n available fountains, for each fountain its beauty and cost are known. There are two types of money in the game: coins and diamonds, so each fountain cost can be either in coins or diamonds. No money changes between the types are allowed. Help Arkady to find two fountains with maximum total beauty so that he can buy both at the same time. Input
The first line contains three integers n, c and d (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) — the number of fountains, the number of coins and diamonds Arkady has. The next n lines describe fountains. Each of these lines contain two integers bi and pi (1 ≤ bi, pi ≤ 100 000) — the beauty and the cost of the i-th fountain, and then a letter "C" or "D", describing in which type of money is the cost of fountain i: in coins or in diamonds, respectively. Output
Print the maximum total beauty of exactly two fountains Arkady can build. If he can't build two fountains, print 0. Examples
input
3 7 6 output
9 input
2 4 5 output
0 input
3 10 10 output
10 Note
In the first example Arkady should build the second fountain with beauty 4, which costs 3 coins. The first fountain he can't build because he don't have enough coins. Also Arkady should build the third fountain with beauty 5 which costs 6 diamonds. Thus the total beauty of built fountains is 9. In the second example there are two fountains, but Arkady can't build both of them, because he needs 5 coins for the first fountain, and Arkady has only 4 coins. 要求建两个喷泉，现在有n个喷泉可以选，每一个喷泉的价格和漂亮度都已经给出，这里有两种货币，硬币和钻石（王者荣耀的感觉，买英雄啊，买两个加起来最强的，你有一定的金币和钻石，用钻石买的英雄肯定有比较强的，也可能没有）。求出他能建的喷泉的方法中最大的漂亮度。 这个我只能想到超时的做法，n^2的，正确的打开方式是树状数组.要建两个喷泉，一共就三种情况，选一个用硬币买的喷泉再选一个用钻石买的喷泉，或者选两个用硬币买的喷泉，或者选两个用钻石买的喷泉。 所以枚举每一个喷泉，然后用树状数组查询出，这样大大降低了复杂度。这样的话二分也可以过应该。看来是时候学一波线段树，树状数组了 来个树状数组入门 假设数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。
来观察这个图：
令这棵树的结点编号为C1，C2...Cn。令每个结点的值为这棵树的值的总和，那么容易发现：
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
...
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
这里有一个有趣的性质：
设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。因为这个区间最后一个元素必然为Ax，
所以很明显：Cn = A(n – 2^k + 1) + ... + An
算这个2^k有一个快捷的办法，定义一个函数如下即可：
利用机器补码特性，也可以写成：
当想要查询一个SUM(n)(求a[n]的和），可以依据如下算法即可：
step1: 令sum = 0，转第二步；
step2: 假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；
step3: 令n = n – lowbit(n)，转第二步。
可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明：
n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。
那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。
所以修改算法如下（给某个结点i加上x）：
step1: 当i > n时，算法结束，否则转第二步；
step2: Ci = Ci + x， i = i + lowbit(i)转第一步。
i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。
对于数组求和来说树状数组简直太快了!
注：
求lowbit(x)的建议公式：
lowbit(x):=x and -x;
或lowbit(x):=x and (x xor (x - 1));
lowbit(x)即为2^k的值。
#include<bits/stdc++.h> using namespace std; const int maxn = 100000; int C[maxn+10],D[maxn+10]; void add(int *tree,int k,int num) { while(k<=maxn) { tree[k] = max(tree[k],num); k+=k&-k; } } int read(int *tree,int k) { int res=0; while(k) { res = max(res,tree[k]); k-=k&-k; } return res; } int main() { int n,c,d,i,j; scanf("%d%d%d",&n,&c,&d); int ans = 0; for(i=1; i<=n; i++) { int b,p; char t[5]; scanf("%d%d%s",&b,&p,t); int maxn; if(t[0] == 'C') { maxn = read(D,d); if(p > c) continue; maxn = max(maxn,read(C,c-p)); add(C,p,b); } else { maxn = read(C,c); if(p > d) continue; maxn = max(maxn,read(D,d-p)); add(D,p,b); } if(maxn) ans = max(ans,maxn + b); } cout << ans << endl; return 0; }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期
今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知
今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道
今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要
我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多
今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不
电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很
我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法
今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win
今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎
请发表评论