当前位置:网站首页>(lightoj - 1349) Aladdin and the optimal invitation (greed)
(lightoj - 1349) Aladdin and the optimal invitation (greed)
2022-07-06 16:25:00 【AC__ dream】
Topic link :Aladdin and the Optimal Invitation | LightOJ
The question : Give you a two-dimensional plane and its n A little bit , Let you output here n The point where the sum of the distances of the points is the smallest , The answer may not be unique , Just output one randomly .
I introduced a warehouse location problem in my blog before , That is to say Give you a straight line , On this straight line n A little bit , Let you find a point on a straight line and make this point here n The sum of the distances of points is the smallest , The conclusion at that time was to take the midpoint , It proves that I have a detailed introduction in the blog of cargo hold location , Interested students can have a look at .
This problem is replaced by finding the minimum value of the sum of distances from a point to some points in the two-dimensional plane , We know Two dimension is actually a superposition of one dimension , So we can divide the two dimensions into two one dimensions , Find the answer of each dimension separately , Just combine , Here is the code :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=50003;
struct node
{
int x,y,t;
}p[N];
bool cmpx(node a,node b)
{
return a.x<b.x;
}
bool cmpy(node a,node b)
{
return a.y<b.y;
}
int n,m,q;
int findx(int x)
{
sort(p+1,p+q+1,cmpx);
int cnt=0,pos=0;
while(cnt<x) cnt+=p[++pos].t;
return p[pos].x;
}
int findy(int x)
{
sort(p+1,p+q+1,cmpy);
int cnt=0,pos=0;
while(cnt<x) cnt+=p[++pos].t;
return p[pos].y;
}
int main()
{
int T;
cin>>T;
for(int _=1;_<=T;_++)
{
scanf("%d%d%d",&n,&m,&q);
int cnt=0;
for(int i=1;i<=q;i++)
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].t),cnt+=p[i].t;
printf("Case %d: %d %d\n",_,findx((cnt+1)>>1),findy((cnt+1)>>1));
}
return 0;
}
边栏推荐
- Install Jupiter notebook under Anaconda
- 顺丰科技智慧物流校园技术挑战赛(无t4)
- Sanic异步框架真的这么强吗?实践中找真理
- Codeforces - 1526C1&&C2 - Potions
- Browser print margin, default / borderless, full 1 page A4
- C language learning notes
- AcWing:第58场周赛
- Sword finger offer II 019 Delete at most one character to get a palindrome
- 1903. Maximum odd number in string
- 969. Pancake sorting
猜你喜欢
1529. Minimum number of suffix flips
C language is the watershed between low-level and high-level
D - function (HDU - 6546) girls' competition
Kubernetes cluster deployment
2027. Minimum number of operations to convert strings
Anaconda下安装Jupyter notebook
Codeforces Round #802(Div. 2)A~D
“鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
Data storage in memory & loading into memory to make the program run
Flask框架配置loguru日志库
随机推荐
The concept of C language array
QT实现窗口渐变消失QPropertyAnimation+进度条
Classic application of stack -- bracket matching problem
B - Code Party (girls' competition)
Advancedinstaller installation package custom action open file
window11 conda安装pytorch过程中遇到的一些问题
力扣:第81场双周赛
去掉input聚焦时的边框
使用jq实现全选 反选 和全不选-冯浩的博客
Basic Q & A of introductory C language
Raspberry pie 4b64 bit system installation miniconda (it took a few days to finally solve it)
1013. Divide the array into three parts equal to and
Raspberry pie 4B installation opencv3.4.0
< li> dot style list style type
Codeforces Round #797 (Div. 3)无F
Acwing - game 55 of the week
1529. Minimum number of suffix flips
Remove the border when input is focused
C basic grammar
Summary of FTP function implemented by qnetworkaccessmanager