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

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从大到小排序?从小到大不确定比我大的在哪里。

好了就到这里,如有错误,请大佬在评论区指出。谢谢!

相关标签: 小技巧

推荐阅读