799C(xjb)

题目链接: http://codeforces.com/problemset/problem/799/C

题意: 有c, d两种货币, 有 n 个货物, 可以用 c 货币或者 d 货币购买, 现在需要买两件货物, 问购买的货物的美丽值最大可为多少.

思路: 只买两件货物, 那么总共有 3 总可能, 买一件 c 一件 d, 买两件 c 或者买两件 d . 取他们的最大值即可.

可以给 c 货物和 d 货物按 p 升序排列, 那么对于买一件 c 一件 d 的情况, 只需要遍历一下 c 货物和 d 货物, 分别取能买到的最大 b 值即可.

对于买两件 c 的情况, 用 vis[k] 存储当前 k 个 c 货币最大可买到的 b 值. 那么可以遍历c 货物的同时更新 vis 数组, 即对于当前 i , vis[k] 存储 [0, i) 中 k 可以买到的最大价值.

那么对于每一个 i , 匹配一下 vis[c - gel_c[i].p] 即可, 然后维护一下 gel_c[i].b + vis[c - gel_c[i].p] 的最大值即可.

对于选两件 d 的情况, 和选两个 c 的情况处理方法相同.

代码:

 #include <iostream>

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 using namespace std;

 const int MAXN = 1e5 + ;

 struct node{

     int b, p;

 }gel_c[MAXN], gel_d[MAXN];

 int vis[MAXN], tag[MAXN];

 bool cmp(node x, node y){

     return x.p < y.p;

 }

 int main(void){

     char op[];

     int n, c, d, indx_c = , indx_d = , ans = ;

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

     for(int i = ; i < n; i++){

         int b, p;

         scanf("%d%d%s", &b, &p, op);

         if(op[] == 'C'){

             gel_c[indx_c].b = b;

             gel_c[indx_c++].p = p;

         }else{

             gel_d[indx_d].b = b;

             gel_d[indx_d++].p = p;

         }

     }

     sort(gel_c, gel_c + indx_c, cmp);

     sort(gel_d, gel_d + indx_d, cmp);

     int cnt1 = , cnt2 = , pos = ;

     for(int i = ; i < indx_c; i++){

         if(gel_c[i].p > c) break;

         cnt1 = max(cnt1, gel_c[i].b);

     }

     for(int i = ; i < indx_d; i++){

         if(gel_d[i].p > d) break;

         cnt2 = max(cnt2, gel_d[i].b);

     }

     if(cnt1 && cnt2) ans = cnt1 + cnt2;

     cnt1 = cnt2 = ;

     for(int i = ; i < indx_c; i++){

         int gg = c - gel_c[i].p;

         if(gg <= ) break;

         int cc = upper_bound(tag, tag + pos, gg) - tag;

         if(cc ==  && i != ) break;

         cc = tag[cc - ];

         if(vis[cc]) ans = max(ans, gel_c[i].b + vis[cc]);

         vis[gel_c[i].p] = max(cnt1, gel_c[i].b);

         tag[pos++] = gel_c[i].p;

         cnt1 = max(cnt1, gel_c[i].b);

     }

     pos = ;

     for(int i = ; i < indx_d; i++){

         int gg = d - gel_d[i].p;

         if(gg <= ) break;

         int cc = upper_bound(tag, tag + pos, gg) - tag;

         if(cc ==  && i != ) break;

         cc = tag[cc - ];

         if(vis[cc]) ans = max(ans, gel_d[i].b + vis[cc]);

         vis[gel_d[i].p] = max(cnt2, gel_d[i].b);

         tag[pos++] = gel_d[i].p;

         cnt2 = max(cnt2, gel_d[i].b);

     }

     printf("%d\n", ans);

     return ;

 }

巴特西

799C(xjb)

最新文章

热门文章