Buy and Resell
题意:
有一个物品有\(n\)个价格,从\(1\)到\(n\)遍历,对于每个价格\(a[i]\),可以花\(a[i]\)购买,或者把现在拥有的物品以\(a[i]\)的价格卖出赚取差价,或者什么都不做,问最终能获得的最大收益以及最大收益下的最小交易次数
思路:
遍历过程中维护一个集合,表示当前可以获得的\(a[i]\)的值(不一定是已经获得的),这些可以获得的\(a[i]\)可能有两种来源,一种就是花钱买的,一种是用集合里的值换的。
对于新的\(a[i]\),如果小于等于集合里最小值,那就加入集合,因为亏本,所以不可能换,这里是花钱买的。
否则,我们就用最小的值把\(a[i]\)换进来,并把差值加进\(ans\)里,这时\(a[i]\)可以有上述两种来源,所以把\(a[i]\)加入集合两次,并打标记区分,此时原来的最小值已经被换出,不在集合中了
对于交易次数,每次换出最小值时判断这个值是否是买进来的,是的话交易次数\(+2\)
集合中被标记为换来的值其实相当于一个暂时的替代品,一个中介,比如\(a\)换\(b\),\(b\)换\(c\),其实最终就是\(a\)换\(c\),\(b\)只是一个中介
每次换出最小值,其实一次交易(买入卖出)并没有完成,因为被标记为换入的\(a[i]\)可能成为最小值被换出,这个操作就延续的原来的交易
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
struct s{
int v, mk;
friend bool operator < (s x, s y){
if(x.v != y.v)
return x.v > y.v;
return x.mk > y.mk;
}
};
int a[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t, n;
cin >> t;
while(t--){
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
priority_queue<s>q;
ll ans = 0, cnt = 0;
for(int i = 1; i <= n; ++i){
if(q.empty()) q.push(s{a[i], 1});
else{
auto x = q.top();
if(x.v >= a[i])
q.push(s{a[i], 1});
else{
ans += a[i] - x.v;
q.pop();
q.push(s{a[i], 1});
q.push(s{a[i], 0});
if(x.mk) cnt += 2;
}
}
}
cout << ans << ' '<< cnt <<'\n';
}
return 0;
}
YJJ's Salesman
题意:
二维平面上\(n\)个点,每个点有权值,从\((0,0)\)到\((1e9,1e9)\),每次移动只能从\((x,y)\)到\((x+1,y)\)或者\((x,y+1)\)或者\((x+1,y+1)\),且只有通过第三种方式到达某个点才能获得该点的权值,问能获得的最大权值
思路:
\(dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + v[i][j])\)
但是数据太大,考虑优化
只考虑有权值的\(n\)个点,对于每个点,状态从该点左下方的最大值转移过来
所以对于每个点,答案就是左下方的矩形\((0,0)-(x-1,y-1)\)和该点权值之和,遍历\(n\)个点取最大即为答案
先对\(n\)个点的纵坐标离散化,然后按横坐标升序,纵坐标降序排列,每个点把纵坐表插入树状数组求前缀最大值
对于当前的点\((x,y)\),先查询树状数组中前缀\([1,y-1]\)的最大值,此时统计的恰好是矩形\((0,0)-(x-1,y-1)\)
因为对于树状数组中大于等于\(y\)的值不影响查询结果,而小于\(y\)且大于等于\(x\)的值还没插入,这就是同一横坐标要从上往下处理的原因
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
struct s {
int x, y, v;
friend bool operator<(s a, s b) {
if (a.x == b.x) return a.y > b.y;
return a.x < b.x;
}
} a[maxn];
int n, t;
ll mx[maxn];
void add(int x, ll val) {
for (int i = x; i <= n; i += i & (-i))
mx[i] = max(mx[i], val);
}
ll ask(int x) {
ll ans = 0;
for (int i = x; i >= 1; i -= i & (-i))
ans = max(ans, mx[i]);
return ans;
}
vector<int> vec;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
while (t--) {
memset(mx, 0, sizeof(mx));
vec.clear();
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].x >> a[i].y >> a[i].v;
vec.push_back(a[i].y);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (int i = 1; i <= n; ++i)
a[i].y = lower_bound(vec.begin(), vec.end(), a[i].y) - vec.begin() + 1;
sort(a + 1, a + 1 + n);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ll x = ask(a[i].y - 1) + a[i].v;
ans = max(ans, x);
add(a[i].y, x);
}
cout << ans << '\n';
}
return 0;
}