Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <limits.h>
- using namespace std;
- typedef long long ll;
- struct DATA{
- ll pos;
- ll group;
- ll self_idx, other_idx;
- DATA(){}
- bool operator<(const DATA& target)const{
- return pos<target.pos;
- }
- };
- vector<DATA> input;
- ll T;
- int main()
- {
- scanf("%lld", &T);
- while(T--){
- ll N, M;
- scanf("%lld%lld", &N, &M);
- input = vector<DATA>(N+M+1);
- for(int i=1;i<=N;i++){
- scanf("%lld", &input[i].pos);
- input[i].group = -1;
- }
- // A그룹 입력
- for(int i=(int)(N+1);i<=M+N;i++){
- scanf("%lld", &input[i].pos);
- input[i].group = 1;
- }
- // B그룹 입력
- sort(input.begin()+1, input.end());
- // 정렬
- vector<ll> asum, rasum, bsum, rbsum;
- asum = vector<ll>(N+M+2);
- rasum = vector<ll>(N+M+2);
- bsum = vector<ll>(N+M+2);
- rbsum = vector<ll>(N+M+2);
- // 누적합 배열 선언
- int aidx=0, bidx=0;
- for(int i=1;i<=N+M;i++){
- if(input[i].group==-1){
- input[i].self_idx=++aidx;
- input[i].other_idx=bidx;
- }else{
- input[i].self_idx=++bidx;
- input[i].other_idx=aidx;
- }
- }
- // 전체 배열에서 상대 인덱스 저장
- for(int i=1;i<=N+M;i++){
- asum[i] = asum[i-1];
- bsum[i] = bsum[i-1];
- if(input[i].group == -1){
- asum[i] += input[i].pos;
- }else{
- bsum[i] += input[i].pos;
- }
- }
- for(int i=(int)(N+M);i>=1;i--){
- rasum[i] = rasum[i+1];
- rbsum[i] = rbsum[i+1];
- if(input[i].group == -1){
- rasum[i] += input[i].pos;
- }else{
- rbsum[i] += input[i].pos;
- }
- }
- // 누적합
- ll min_idx=0;
- ll min_val = LONG_LONG_MAX;
- for(int i=1;i<=N+M;i++){
- ll resa = 0, resb = 0;
- if(input[i].group == -1){
- if(i>1){
- resa += llabs(asum[i-1]-input[i].pos*(input[i].self_idx-1));
- resb += llabs(bsum[i-1]-input[i].pos*(input[i].other_idx));
- }
- if(i<N+M){
- resa += llabs(rasum[i+1]-input[i].pos*(N-input[i].self_idx));
- resb += llabs(rbsum[i+1]-input[i].pos*(M-input[i].other_idx));
- }
- }else{
- if(i>1){
- resa += llabs(asum[i-1]-input[i].pos*(input[i].other_idx));
- resb += llabs(bsum[i-1]-input[i].pos*(input[i].self_idx-1));
- }
- if(i<N+M){
- resa += llabs(rasum[i+1]-input[i].pos*(N-input[i].other_idx));
- resb += llabs(rbsum[i+1]-input[i].pos*(M-input[i].self_idx));
- }
- }
- ll res = resa*M+resb*N;
- // printf("i:%d val:%d %lld\n", i, input[i].pos, res);
- if(res<min_val){
- min_idx = i;
- min_val = res;
- }
- }
- // 누적합 배열 이용해서 한 정점에서 다른 모든 정점까지의 거리의 합 계산
- printf("%lld.0\n", input[min_idx].pos);
- }
- return 0;
- }
- // 3 2 2 7 12 5 8
Add Comment
Please, Sign In to add comment