hdu-6438-贪心
Buy and Resell
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1160 Accepted Submission(s): 369
1. spend ai dollars to buy a Power Cube
2. resell a Power Cube and get ai dollars if he has at least one Power Cube
3. do nothing
Obviously, Noswal can own more than one Power Cubes at the same time. After going to the n cities, he will go back home and stay away from the cops. He wants to know the maximum profit he can earn. In the meanwhile, to lower the risks, he wants to minimize the times of trading (include buy and sell) to get the maximum profit. Noswal is a foxy and successful businessman so you can assume that he has infinity money at the beginning.
The first line has an integer n. (1≤n≤105)
The second line has n integers a1,a2,…,an where ai means the trading price (buy or sell) of the Power Cube in the i-th city. (1≤ai≤109)
It is guaranteed that the sum of all n is no more than 5×105.
4
1 2 10 9
5
9 5 9 10 5
2
2 1
5 2
0 0
In the first case, he will buy in 1, 2 and resell in 3, 4. profit = - 1 - 2 + 10 + 9 = 16
In the second case, he will buy in 2 and resell in 4. profit = - 5 + 10 = 5
In the third case, he will do nothing and earn nothing. profit = 0
#include<bits/stdc++.h>
using namespace std;
#define LL long long
map<int,int>M;
int main(){
int t,n,m,i,j,k,a;
cin>>t;
while(t--){
scanf("%d",&n);
priority_queue<int,vector<int>,greater<int> >q;
M.clear();
LL s1=,s2=;
for(i=;i<=n;++i){
scanf("%d",&a);
if(q.empty() || q.top()>=a){
q.push(a);
}
else{
s1+=a-q.top();
if(M[q.top()]==){
s2++;
}
else{
M[q.top()]--;
}
q.pop();
q.push(a);
q.push(a);
M[a]++;
} }
//cout<<s1<<endl;
printf("%lld %lld\n",s1,s2*);
}
return ;
}
最新文章
- .NET跨平台实践:用C#开发Linux守护进程
- zookeeper安装配置
- Counting-Sort
- OpenCV 3.0 VS2010 Configuration
- MTK+Android编译
- javascript callback函数的理解与使用
- 关于PHP Websocket 错误: ";stream_select(): You MUST recompile PHP with a larger value of FD_SETSIZE"; 的解决方案
- tomcat错误信息解决方案【严重:StandardServer.await: create[8005]
- meta 标签整理
- datatables表格
- 微信小程序开发基础知识总结
- PHP实现WebService的简单示例和实现步骤
- Java 多线程之线程池的使用
- Vue路由学习心得
- 杭电1532----Drainage Ditches『最大流』
- [luogu P3953] [noip2017 d1t3] 逛公园
- CSS控制文字显示一行,超出显示省略号
- jquery中选择checkbox拼接成字符串,然后到后台拆分取值
- golang简单实现jwt验证(beego、xorm、jwt)
- BZOJ 1834 网络扩容 最大流+最小费用流