NLO
程序员文章站
2022-04-28 15:49:25
...
(不好意思今天没有链接)
(比 )暴( 利 ) 力的做法想必已想出来了:建一个G数组存(i,j)上第几个UFO编号(最后的),再计算。然而TLE+MLE。
一般这种题的思路都是将多余的空格的空间省掉。我当时只想到将UFO覆盖的点用vector存起来,可算了算,还是会TLE+MLE(癫狂)。
正解来了!
我们以一行为界限,将UFO以左右边界的形式储存,这样的时间复杂度应是O(n*k)。
上马!
#include<cstdio>
#include<queue>
#include<set>
#include<cmath>
using namespace std;
typedef long long ll;
struct node {
int x, y, r;
}s[102];
struct hhh {
int col, id;
bool f;
bool operator < (const hhh &t) const {
if(col == t.col)//C
return id < t.id;
return col > t.col;
}
};
priority_queue <hhh> q;
set <int, greater <int> > st;//A
int n, m, k;
ll ans;
int main() {
int tmp, tt;
scanf("%d %d %d", &n, &m, &k);
for(int i = 1; i <= k; i ++) {
scanf("%d %d %d", &s[i].x, &s[i].y, &s[i].r);
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= k; j ++) {
if(s[j].x + s[j].r < i || s[j].x - s[j].r > i)
continue;
tt = (int) sqrt(1ll * s[j].r * s[j].r - 1ll * (i - s[j].x) * (i - s[j].x));
q.push((hhh) {s[j].y - tt, j, 1});
q.push((hhh) {s[j].y + tt + 1, j, 0});
}
tmp = 1;
while(! q.empty()) {
hhh t = q.top();
q.pop();
if(t.f == 1) {
if(st.empty()) {
ans += 1ll * (t.col - tmp) * k;
tmp = t.col;
}
else if(t.id > * st.begin()) {
ans += 1ll * (t.col - tmp) * (k - * st.begin());
tmp = t.col;
}
st.insert(t.id);
}
else {
if(* st.begin() == t.id) {
ans += 1ll * (t.col - tmp) * (k - t.id);
tmp = t.col;
}
st.erase(t.id);
}
}
ans += 1ll * (m - tmp + 1) * k;//B
}
printf("%lld\n", ans);
return 0;
}
注:
A:注意set与queue的排序。
B:后面还有一段未覆盖的。
C:为什么相同col时用id从大到小排序?从小到大不确定比我大的在哪里。
好了就到这里,如有错误,请大佬在评论区指出。谢谢!
下一篇: Django—跨域请求(jsonp)
推荐阅读