2018 CCPC 网络赛

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;
}
上一篇:2020河南省ccpc省赛太阳轰炸


下一篇:JAVA系列之JNI,你了解了吗?