肇庆网站建设制作,网页设计需求分析范文,策划公司宣传语,织梦 网站设计题目链接 汽车-腾讯2023笔试(codefun2000)
题目内容 现在塔子哥有 n 个汽车#xff0c;所有的汽车都在数轴上#xff0c;每个汽车有1.位置 pos 2.速度 v #xff0c;它们都以在数轴上以向右为正方向作匀速直线运动。 塔子哥可以进行任意次以下操作#xff1a;选择两个汽车…题目链接 汽车-腾讯2023笔试(codefun2000)
题目内容 现在塔子哥有 n 个汽车所有的汽车都在数轴上每个汽车有1.位置 pos 2.速度 v 它们都以在数轴上以向右为正方向作匀速直线运动。 塔子哥可以进行任意次以下操作选择两个汽车交换它们的初始位置但不交换速度。 塔子哥希望操作完毕后的汽车永远不会相撞请你帮塔子哥输出交换后每个汽车的初始位置和初始速度。(需要按输入顺序的汽车编号输出) 输入描述 第一行一个整数 n 。 接下来 n 行每行两个整数 pos v 。 初始情况下保证没有两个汽车的位置相同。 1 ≤ n ≤ 1 0 5 , − 1 0 9 ≤ p o s , v ≤ 1 0 9 1≤n≤10^5,−10^9≤pos,v≤10^9 1≤n≤105,−109≤pos,v≤109 输出描述 输出 n 行每行输出两个整数代表交换后每个汽车的位置和速度 合法解不止一个输出任意合法解即可。 样例1
输入 3 11 17 15 -1 6 20 输出 11 17 6 -1 15 20 样例2
输入 5 1 6 4 -2 11 6 15 -9 10 2 输出 11 6 4 -2 15 6 1 -9 10 2 题解1
#includebits/stdc.h
using namespace std;
const int N 1e5 10;int n;
struct Node{int idx; // 汽车编号int pos; // 汽车的位置int v; // 汽车的速度
}a[N], b[N], c[N];bool cmp1(const Node A, const Node B){if(A.v ! B.v) return A.v B.v;return A.pos B.pos;
}
bool cmp2(const Node A, const Node B){return A.pos B.pos;
}/*
题解 将速度按升序排序位置在左边的速度小位置在右边的速度大这样就可以保证所有的汽车不会相撞
*/
int main(){scanf(%d, n);for(int i 1; i n; i){scanf(%d%d, a[i].pos, a[i].v);a[i].idx i;} for(int i 1; i n; i){c[i].idx b[i].idx a[i].idx;c[i].pos b[i].pos a[i].pos;c[i].v b[i].v a[i].v;}sort(b 1, b n 1, cmp1); // 将速度按升序排序 sort(c 1, c n 1, cmp2); // 将位置按升序排序 for(int i 1; i n; i){a[b[i].idx].pos c[i].pos; // a[b[i].idx]表示编号为b[i].idx的汽车的初始位置是c[i].pos }for(int i 1; i n; i){printf(%d %d\n, a[i].pos, a[i].v);}return 0;
}