ACM-ICPC 2018 徐州赛区网络预赛 G - Trace
程序员文章站
2022-03-13 16:37:17
...
题意一波又一波的浪打到沙滩上,问覆盖的周长是多少。
每一波浪都会增加新的周长,题意说的很清楚了,并没有能完全覆盖另一波的浪,也没有被另一波完全覆盖的浪...
所以说
2 2
1 1
这样的数据是没有的
//从后往前遍历,如果比最小的浪还小,就加入,否则就计算出大于等于的浪-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;
}
下一篇: 问题 J: Master of GCD
推荐阅读
-
ACM-ICPC 2018 徐州赛区网络预赛 H - Ryuji doesn't want to study
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study(线段树区间求和)
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study—— 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 H Ryuji doesn't want to study(线段树 两种做法)
-
【ACM-ICPC 2018 徐州赛区网络预赛】H题 Features Track ---- 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (线段树维护)
-
计蒜客 Trace(2018 ICPC亚洲区域赛网络赛 徐州 G)(线段树)
-
ACM-ICPC 2018 徐州赛区网络预赛 Trace
-
Trace-----ACM-ICPC 2018 徐州赛区网络预赛
-
ACM-ICPC 2018 沈阳赛区网络预赛 F题 Fantastic Graph