【HDOJ】2385 Stock

摘要:
水问题,反向做+优先队列。

水题,逆向做+优先级队列。

  1 /* 2385 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 typedef struct node_t {
 44     int p, m;
 45     
 46     friend bool operator< (const node_t& a, const node_t& b) {
 47         return a.p < b.p;
 48     }
 49     
 50 } node_t;
 51 
 52 const int maxn = 1e5+5;
 53 node_t nd[maxn];
 54 int X[maxn];
 55 int n;
 56 
 57 void solve() {
 58     priority_queue<node_t> Q;
 59     node_t d;
 60     int x;
 61     int ans = 0;
 62     
 63     per(i, 0, n) {
 64         Q.push(nd[i]);
 65         x = X[i];
 66         while (!Q.empty() && x>0) {
 67             d = Q.top();
 68             Q.pop();
 69             if (d.m > x) {
 70                 d.m -= x;
 71                 ans += d.p * x;
 72                 x = 0;
 73                 Q.push(d);
 74             } else {
 75                 x -= d.m;
 76                 ans += d.p * d.m;
 77             }
 78         }
 79     }
 80     
 81     printf("%d
", ans);
 82 }
 83 
 84 int main() {
 85     ios::sync_with_stdio(false);
 86     #ifndef ONLINE_JUDGE
 87         freopen("data.in", "r", stdin);
 88         freopen("data.out", "w", stdout);
 89     #endif
 90     
 91     int t;
 92     
 93     scanf("%d", &t);
 94     while (t--) {
 95         scanf("%d", &n);
 96         rep(i, 0, n)
 97             scanf("%d %d %d", &X[i], &nd[i].p, &nd[i].m);
 98         solve();    
 99     }
100     
101     #ifndef ONLINE_JUDGE
102         printf("time = %d.
", (int)clock());
103     #endif
104     
105     return 0;
106 }

免责声明:文章转载自《【HDOJ】2385 Stock》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇【HDOJ】4393 Throw nailsWinCE 自由拼音输入法的测试下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

产品群体互联网产品设计规划产品群体

最近使用开发的过程中出现了一个小问题,顺便记录一下原因和方法--产品群体 找准标目户用群体 产品所面临的群体是什么? 他们的同共特征是什么? 标目户用群体的市场有多大,是不是能实现可持续开展? 解理行业竞争 产品内容是不是有特独的值价 与竞争者的优势在哪里? 如何鉴戒并越超敌手 在功能、内容以及节目的创新的地方? 做久长的开展规划 产品能给团队带来...

请问一下哪有机械键盘的实体店可以体验一下? 外设 Chiphell 分享与交流用户体验的最佳平台 Powered by Discuz!

请问一下哪有机械键盘的实体店可以体验一下? - 外设 - Chiphell - 分享与交流用户体验的最佳平台 - Powered by Discuz! [键盘]请问一下哪有机械键盘的实体店可以体验一下?[复制链接] stavent stavent当前离线 天使 天使, 积分 204, 距离下一级还需 296...

Lua 语言和C/C++集成调研小结

Lua 语言和C/C++集成调研小结 - hzqhbc的专栏 - 博客频道 - CSDN.NET Lua 语言和C/C++集成调研小结 分类:luaC++2012-04-28 10:4810人阅读评论(0)收藏举报 原文转自http://bbs.luaer.cn/read-Lua-tid-58-fpage-4.html 1. Lua的特点Lua...

Java 上下文与依赖注入(JSR 299)[1]

Java 上下文与依赖注入(JSR 299)[1] 转载请保留作者信息: 作者:88250 Blog:http:/blog.csdn.net/DL88250 MSN & Gmail & QQ:DL88250@gmail.com 摘要 本文从 JSR 299 规范入手,整理并翻译了该规范中非常重要的概念,并结合一些短小的例子对 JSR...

新建Android项目时使用project from existing source导入已经存在的项目报 AndroidManifest.xml file missing错误解决方案

出错经过 为了查看<sdk>/platforms/<android-version>/samples/文件夹下的Android自带的经典例子,于是将要看的例子导入到eclipse的workspace当中,在利用eclipse的import功能将项目导入到eclipse,但是报了“no projects found to...

c bdmap结构

1 #include "bdmap.h"2 typedef struct _bdmap_node3 {4 char *key;5 int *value;6 struct _bdmap_node *next;7 }bdmap_node;8 9 struct _bdmap10 {11 bdmap_node *first;12 bdmap_node *curren...