欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ACM-ICPC 2018 徐州赛区网络预赛 - G Trace - 思维

程序员文章站 2022-03-24 10:45:18
...

题目连接:https://nanti.jisuanke.com/t/31459

思路:

我们可以反向考虑,这样简单一点,从最后一次wave开始,每次加上前一次比这几次多出来的部分。

而且可以把横、纵坐标分开来求。

步骤:

1、建一个set

2、从set里找出第一个>=a[i]的值

(1)若set是空的或者a[i]是set里最小的值,则ans+=a[i]

(2)反之,ans+=最大的且小于a[i]的值

3、把a[i]插入set里

ACM-ICPC 2018 徐州赛区网络预赛 - G Trace - 思维

代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<string>
#include<cstring>
#define ll long long
using namespace std;
const int N=50005;
int n;
ll X[N],Y[N];

ll solve(ll a[]){
    set<int>used;
    set<int>::iterator it;
    ll ans=0;
    for(int i=n;i>=1;i--){
        it=used.lower_bound(a[i]);
        if(it==used.begin())ans+=a[i];
        else{
            it--;
            ans+=a[i]-*it;
        }
        used.insert(a[i]);
    }
    return ans;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&X[i],&Y[i]);
    }
    ll ans=solve(X)+solve(Y);
    printf("%lld\n",ans);
}

 

 

相关标签: 思维