上海计算机学会2023年12月月赛C++乙组T1移动向量
发布时间
阅读量：
阅读量
移动向量
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n 个二维向量，其中第 i 个向量记作 (xi,yi)。每个向量对应一种移动操作，其中第 i 个向量表示将点 (s,t) 移动到 (s+xi,t+yi) 。
请从中挑选任意数量的向量，使得从原点出发的点，经过向量的移动之后，终点的 x 坐标的绝对值与 y 坐标的绝对值之和达到最大。
输入格式
- 单个整数：表示 n
- 第二行到第 n+1 行：每行两个整数 xi 与 yi。
输出格式
- 单个整数：表示终点的x坐标绝对值与y坐标绝对值之和的最大值。
数据范围
- 对于 30% 的数据，1≤n≤20
- 对于 60% 的数据，1≤n≤500
- 对于 100% 的数据，1≤n≤300,000
- −109≤xi,yi≤109
样例数据
输入:
4
-100 99
1 100
-1 -100
100 -99
输出:
298
说明:
(-1 -100)
(100 -99)
解析：
想要x绝对值加y绝对值最大,求最大值对于结果有四种情况
1.若结果为x正y正：那么向量只要x+y>0 即增加结果的最大值；
2.若结果为x负y负：那么向量只要x+y<0 即增加结果的最大值
3.若结果为x正y负：那么向量只要x-y>0 即增加结果的最大值
4.若结果为x负y正：那么向量只要x-y<0 即增加结果的最大值
将所有向量分别按x+y和x-y排序，然后分别计算最大值，
然后输出这四个最大值中的最大值，即为答案。
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int x[300005];
int y[300005];
long long ans1=0,ans2=0,ans3=0,ans4=0;//四个最大值
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;i++){
if (x[i]+y[i]>0) ans1+=x[i]+y[i];
if (x[i]-y[i]>0) ans2+=x[i]-y[i];
if (-x[i]+y[i]>0) ans3+=-x[i]+y[i];
if (-x[i]-y[i]>0) ans4+=-x[i]-y[i];
}
cout<<max(max(ans1,ans2),max(ans3,ans4));//输出四个最大值中的最大值
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~