Hướng dẫn giải của 2023D. Vị trí gặp nhau
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Gợi ý 1
Bài này là một bài tập về median
Gợi ý 2
Hãy thử sắp xếp lại mảng và thử duyệt trâu để tính toán tổng khoảng cách di chuyển từ mỗi vị trí thấp nhất tới vị trí cao nhất là bao nhiêu.
Lời giải
Ta có đáp án của bài tập này là những vị trí từ phần từ p[⌊(n-1)/2⌋] tới p[⌊(n)/2⌋] của mảng p (sau khi mảng p đã được sắp xếp theo chiều không giảm).
Code
/**
* Create: Thursday 2023-12-21-21.58.46 GMT+7
* Title : vi tri gap nhau
* Author:
*****/
#include <bits/stdc++.h>
#line 10 "tranxuantruong"
#ifndef MY_TEMPLATE
#define TranXuanTruong main()
#define Get_better(...) ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
template <typename T> ostream& operator << (ostream& os, const stack <T> &stack_) {os << "["; int n = (int) stack_.size(); vector <T> archive (n); stack <T> stackCopy_ (stack_); for (int i=0; i<n; ++i) {archive[stackCopy_.size()-1]=stackCopy_.top(); stackCopy_.pop();} if (!archive.empty()) {for (auto it=archive.begin(); it!=archive.end()-1; ++it) {os <<*it <<", ";} os <<archive.back();} os <<" "; return os;}
template <typename T> ostream& operator << (ostream& os, const queue <T> &queue_) {os << "->["; int n = (int) queue_.size(); vector <T> archive (n); queue <T> queueCopy_ (queue_); for (int i=0; i<n; ++i) {archive[queueCopy_.size()-1]=queueCopy_ .front(); queueCopy_.pop();} if (!archive.empty()) {for (auto it=archive.begin(); it!=archive.end()-1; ++it) {os <<*it <<", ";} os <<archive.back();} os <<" "; return os;}
template <typename T> ostream& operator << (ostream& os, const priority_queue <T,vector<T>,greater<T>>&Queue_) {os << "["; int n = (int) Queue_.size(); vector <T> archive (n); priority_queue<T,vector<T>,greater<T>> QueueCopy_ (Queue_); for (int i=0; i<n; ++i) {archive[QueueCopy_.size()-1]=QueueCopy_.top(); QueueCopy_.pop();} if (!archive.empty()) {for (auto it=archive.begin(); it!=archive.end()-1; ++it) {os <<*it <<", ";} os <<archive.back();} os <<" "; return os;}
template <typename T> ostream& operator << (ostream& os, const priority_queue <T> &Queue_) {os << "["; int n = (int) Queue_.size(); vector <T> archive (n); priority_queue<T> QueueCopy_ (Queue_); for (int i=0; i<n; ++i) {archive[QueueCopy_.size()-1]=QueueCopy_.top(); QueueCopy_.pop();} if (!archive.empty()) {for (auto it=archive.begin(); it!=archive.end()-1; ++it) {os <<*it <<", ";} os <<archive.back();} os <<" "; return os;}
template <typename T> ostream& operator << (ostream& os, const vector <T> &vector_) {os << "["; if (!vector_ .empty()) {for (auto it = vector_ .begin(), i=0; i< (int) vector_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (vector_ .rbegin());} os << "]"; return os;}
template <typename T> ostream& operator << (ostream& os, const deque <T> &deque_) {os << "["; if (!deque_ .empty()) {for (auto it = deque_ .begin(), i=0; i< (int) deque_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (deque_ .rbegin());} os << "]"; return os;}
template <typename T> ostream& operator << (ostream& os, const set <T> &set_) {os << "["; if (!set_ .empty()) {for (auto it = set_ .begin(), i=0; i< (int) set_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (set_ .rbegin());} os << "]"; return os;}
template <typename T> ostream& operator << (ostream& os, const multiset <T> &multiSet_) {os << "["; if (!multiSet_.empty()) {for (auto it = multiSet_.begin(), i=0; i< (int) multiSet_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (multiSet_ .rbegin());} os << "]"; return os;}
template <typename T, typename _> ostream& operator << (ostream& os, const map <T, _> &map_) {os << "["; if (!map_ .empty()) {for (auto it = map_ .begin(), i=0; i< (int) map_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (map_ .rbegin());} os << "]"; return os;}
template <typename T, typename _> ostream& operator << (ostream& os, const multimap <T, _> &multiMap_) {os << "["; if (!multiMap_.empty()) {for (auto it = multiMap_.begin(), i=0; i< (int) multiMap_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (multiMap_ .rbegin());} os << "]"; return os;}
template <typename T, typename _> ostream& operator << (ostream& os, const pair <T, _> &pair_) {os << "{"; {os <<pair_.first; os <<":"; os <<pair_.second;} os << "}"; return os;}
template <typename T> void quick_debug (ostream& os, const char *name, const T &value) {os <<" " << name <<" = " <<value <<endl <<endl;};
template <typename T, typename... Args> void quick_debug (ostream& os, const char *name, const T &value, Args&&... args) {os <<" "; while (*name != ',') {os << *name++;} os << " = " << value << endl; quick_debug (os, name + 1, args...);};
; istream& operator >> (istream& is, __int128 & x) { __int128 sign=1; x=0; char c=is.get(); for( ;!isdigit(c); ){if(c=='-'){sign=-1;}c=is.get();} for( ;isdigit(c); ){x=(x<<3)+(x<<1)+(c^'0');c=is.get();} x*=sign; return is; }
; ostream& operator << (ostream& os, __int128 x) { if(x==0){return os<<"0";} int sign=1; if(x<0){sign=-1; x=-x;} string s=""; for( ;x!=0; ){s+='0'+x%10;x/=10;} if(sign<0){s+='-';} reverse(s.begin(), s.end()); return os<<s;}
#define endl '\n'
#define int __int128
#define hien(...) cerr <<__LINE__ <<" " __FILE__ ":" <<endl; quick_debug (cerr, " "#__VA_ARGS__, __VA_ARGS__)
#endif
TranXuanTruong{
Get_better(học thêm một chút nữa đi, 9000);
int t; cin >> t;
for(int i=0; i<t; ++i){
int n; cin >> n;
vector <int> a(n);
for(int i=0; i<n; ++i){
cin >> a[i];
}
sort(a.begin(), a.end());
if(n%2==1){
int K=1;
cout <<K <<endl;
cout <<a[n/2] <<endl;
}
else{
int x=a[(n-1)/2];
int y=a[n/2];
int K=y-x+1;
cout <<K <<endl;
for(int i=0, to=min((int)10, K); i<to; ++i){
cout <<x <<" ";
++x;
}
cout <<endl;
}
}
return 0;
}
Bình luận