极坐标扫描+队列+贪心只能过一个样例
查看原帖
极坐标扫描+队列+贪心只能过一个样例
94304
Sleep_Sheep楼主2023/4/7 15:36

D不出来,不D了

#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;
typedef pair<int, int> pii;
const int N = 2 * 1e5 + 10;

int w[N], ans[N];
pair<double, int> angle[N];
double d[N];
long long seq, l, n;

double get_distance(long long x, long long  y)
{
    return sqrt(x * x + y * y);
}

// 先排角,角一样排距离
bool cmp(pair<double, int>& a, pair<double, int>& b)
{
    if (a.first != b.first) return a.first < b.first;
    else return d[a.second] < d[b.second];
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> n >> l;
    for (int i = 0; i < n;i ++)
    {
        int x, y;
        cin >> x >> y >> w[i];
        double theta = atan2(x, y);
        if (theta < 0) {
        theta += 2 * M_PI;  // 将负值的极角转换为正值的极角
    }
        angle[i] = {theta * 180 / M_PI, i};
        d[i] = get_distance(x, y);
    }
    queue<pair<double, int>> q; 
    sort(angle, angle + n, cmp);
    for (int i = 0; i < n; i ++)
    {
        q.push(angle[i]);
    }
    
    
    int sz = q.size(), prev_a = -1;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        int a = t.first, i = t.second;
        if (a <= prev_a)
        {
            if (sz == q.size()) break;
            sz = q.size();
        }
        if (d[i] <= l)
        {
            // cout << i << ' ' << prev_a << ' ' << a << endl;
            l += w[i];
            if (prev_a == a) ans[i] = seq;
            else {ans[i] = n - q.size(); seq = n - q.size();}
        }
        else
        {
            q.push(t);
        }
        prev_a = a;
        
    }
    for (int i = 0; i < n ; i ++)
    {
        if (ans[i]) cout << ans[i] << ' ';
        else cout << -1 << ' ';
    }
    
    
    return 0;
}
2023/4/7 15:36
加载中...