题解：P14966 Staring at Stars

· · 题解

本人数学很菜，推不出来 t = 1 时答案一定不劣，所以有以下做法。

题目有两个关键的值 t 和 h，我们要明白当 t 和 h 同时是 k 的因数时，才可能达到情绪值最大，不可能去选更小的数，这个应该很好理解。

所以对于每组数据，枚举 k 的因数 t 和 h，同时枚举每颗流星的情况，选出最大的情绪值既可。这种做法的时间复杂度是 O(n\sqrt{k})，可以通过此题。

那么枚举每颗流星的情况具体应该怎么做呢？

首先讲排序，排序规则为：

bool cmp(node p,node q){
    if(p.x != q.x) return p.x < q.x;
    if(p.y != q.y) return p.y < q.y;
    return false;
}

这样就把坐标同一 x 的流星放在了一起，并且 y 也是有序的，方便用双指针维护区间和计算答案。

其次需要去重，因为题目说了位置重复的以最后输入的星星算，前面的会被挡住。重复的坐标只需要最后出现的，所以我们先翻转数组，再 unique 去重。接着用一个数组记录前缀和。

最后就可以计算答案啦，这里单调性很显然，所以我用了双指针，当 x 两两不一致或者 y 的差值超过 t 就计算答案。

代码有两个小细节是：

  1. 翻转数组用 reverse 数据量大时会超时，貌似是因为 reverse 本质是互换位置，会重复扫描内存，自己写个循环就好了。
  2. 枚举流星时在最后设置一个不可能达到的值方便处理数据。

以下是完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10; 
typedef long long ll;
struct node{
    ll x,y,d;
    bool operator == (const node& z){//重载运算符 
        return x == z.x && y == z.y;
    }
};
node a[N],b[N];
int t,n,k;
ll sum[N];
bool cmp(node p,node q){
    if(p.x != q.x) return p.x < q.x;
    if(p.y != q.y) return p.y < q.y;
    return false;
}
int main(){
    cin>>t;
    while(t--){
        ll ans = 0; 
        int pos = 1;//去重后的下标 
        memset(sum,0,sizeof(sum));
        cin>>n>>k;
        for(int i = 1; i <= n; i++) 
            cin>>b[i].x>>b[i].y>>b[i].d;
        for(int i = 1; i <= n; i++){//翻转不能用reverse,会超时 
            int t = n-i+1;
            a[i] = b[t];
        } 
        sort(a+1,a+1+n,cmp);
        auto last = unique(a+1,a+1+n);//排序去重
        for(auto i = a+1; i != last; i++,pos++){
            sum[pos] = sum[pos-1]+a[pos].d;
        }
        a[pos].d = 1e18; a[pos].x = 1e18; a[pos].y = 1e18;//不可能达到的值 
        for(ll t = 1; t*t <= k; t++){
            ll h = k/t;
            for(ll l = 1, r = 1; l < pos && r <= pos; ){//多看一个 
                if(l == r) {r++; continue;}
                if(a[l].x != a[r].x){//不在同一x
                    ans = max(ans,(sum[r-1] - sum[l-1])*h);
                    l = r; continue;
                }
                if(a[r].y - a[l].y > t){//y差值超过t 
                    ans = max(ans,(sum[r-1] - sum[l-1])*h);
                    l = r; continue;
                }
                if(a[r].y - a[l].y <= t) r++;
            }
        }
        cout<<ans<<'\n'; 
    }
    return 0;
}