网站整体色彩的建设,哪个找房网站好,网站关键词seo费用,萝岗电子商务网站建设题目
题意#xff1a;
n个宝石#xff0c;宝石的买入或卖出价格固定#xff0c;一天只能到一个珠宝商店#xff08;从左到右#xff09;#xff0c;问最大利润是多少#xff1f;在保证最大利润的同时最少交换次数是多少#xff1f;
题解#xff1a;
题目有两问
n个宝石宝石的买入或卖出价格固定一天只能到一个珠宝商店从左到右问最大利润是多少在保证最大利润的同时最少交换次数是多少
题解
题目有两问一个是求利润一个是求次数 利润就是低价买高价卖就行 比如1 2 101的时候买2的时候卖2的时候买10的时候卖这样一共挣了189但是如果我们1的时候买10的时候卖也是挣9而且次数还少一次 我们该如何记录最少次数? 利用优先队列 首先我们计算最大利润时就用第一个步骤即1买2卖2买10卖当我们卖完一个宝石时就标记一下若次元素再次出现在队首就说明出现了1 2 10的情况。。然后pop原本加入当前的即弹出2加入10这样始终可以保持最佳 最后根据剩余标记情况计算交换次数 也就是每个宝石分为两个 其实我们要找的就是递增关系
代码
#includebits/stdc.h
#define ll long long
#define PII pairint,int
using namespace std;
const int N 1e65;
const int mod 1e97;
const int INF 0x3f3f3f3f;
struct node{ll num,index;node(ll a,ll b){num a;index b;}friend bool operator (node a,node b){if(a.num b.num) return a.index b.index; //从低到高未标记的在前面 return a.num b.num;//价格从高到低 }
};
priority_queue node q;
int main()
{ll t,p,i,j,k,n,x;cint;while(t--){cinn;ll ans 0,count 0;for(i 1;i n;i){cinx;q.push(node(x,0)); node temp q.top();if(x temp.num)//如果卖出价钱比已买的最高价钱还高 {ans x-temp.num;//卖出 q.pop();q.push(node(x,1));//标记后加入}}while(!q.empty()){if(q.top().index) count;q.pop();}printf(%lld %lld\n,ans,count*2);}
}
