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

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

程序员文章站 2022-03-13 16:37:17
...

题意一波又一波的浪打到沙滩上,问覆盖的周长是多少。

每一波浪都会增加新的周长,题意说的很清楚了,并没有能完全覆盖另一波的浪,也没有被另一波完全覆盖的浪...

所以说

2 2 

1 1 

这样的数据是没有的

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

//从后往前遍历,如果比最小的浪还小,就加入,否则就计算出大于等于的浪-1(地址减一)的浪,然后加上差值,就是伸出去的浪,interstring



#include<bits/stdc++.h>
using namespace std;
vector<int> vc1;
vector<int> vc2;
long long  solve(int temp)
{
    long long  ans = 0;
    set<int> st;
    if(temp == 1)
    {
        int n = vc1.size();
        for(int i = n - 1;i >= 0;i--)
        {
            set<int>::iterator s = st.lower_bound(vc1[i]);
            if(s == st.begin())
            {
                ans += vc1[i];
            }
            else
            {
                s--;
                ans += vc1[i] - *s;
            }
            st.insert(vc1[i]);
        }

    }
    else
    {
        int n = vc2.size();
        for(int i = n-1;i >= 0;i--)
        {
            set<int>::iterator s = st.lower_bound(vc2[i]);
            if(s == st.begin())
            {
                ans += vc2[i];
            }
            else
            {
                s--;
                ans += vc2[i] - *s;
            }
            st.insert(vc2[i]);
        }

    }
    return ans;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 0 ;i <  n ; i ++)
    {
        int x,y;
        cin >> x >> y;
        vc1.push_back(x);
        vc2.push_back(y);
    }
    cout << solve(1) + solve(2) << endl;
}