解题思路:
没学几天算法 不要喷,就是排序之后 放到队列里,然后扫过去
注意事项:
参考代码:
#include<bits/stdc++.h>
using namespace std;
struct Point {
long long x;
long long y;
long long value;
int position;
};
bool compareByAngle(const Point& p1, const Point& p2) {
double angle_a = 1.5708 - atan2(p1.y, p1.x);
double angle_b = 1.5708 - atan2(p2.y, p2.x);
if (angle_a < 0) {
angle_a = 1.5708 * 4 + angle_a;
}
if (angle_b < 0) {
angle_b = 1.5708 * 4 + angle_b;
}
if (angle_a == angle_b) {
double ak1 = p1.x / (double)100000 * p1.x + p1.y / (double)100000 * p1.y;
double ak2 = p2.x / (double)100000 * p2.x + p2.y / (double)100000 * p2.y;
return ak1 < ak2;
}
return angle_a < angle_b;
}
int main()
{
int n;
long long slen;
cin >> n >> slen;
vector<int> sequen(n, -1);
vector<Point> p(n);
queue<Point> q;
for (int i = 0; i < n; i++) {
cin >> p[i].x >> p[i].y >> p[i].value;
p[i].position = i;
}
sort(p.begin(), p.end(), compareByAngle);
for (int i = 0; i < n; i++) {
q.push(p[i]);
}
int not_stop = 1, num = 0, same = 0;
double last_angle = -100;
while(not_stop) {
not_stop = 0;
int q_len = q.size();
for (int i = 0; i < q_len; i++) {
Point entity = q.front();
q.pop();
if (entity.x / (double)slen * entity.x + entity.y / (double)slen * entity.y <= slen) {
slen += entity.value;
not_stop = 1;
if (last_angle != atan2(entity.y, entity.x)) {
last_angle = atan2(entity.y, entity.x);
num = num + same + 1;
same = 0;
sequen[entity.position] = num;
}
else {
sequen[entity.position] = num;
same++;
}
}
else {
q.push(entity);
}
}
}
for (int& i : sequen) {
cout << i << " ";
}
return 0;
}
0.0分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复