[AtCoder] [經典競程 90 題] 014 - We Used to Sing a Song Together（★3）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_n
題目大意:
有 $N$ 個國小生要去上小學，並且剛好也有 $N$ 個小學。一個住在 $A_i$ 的國小生要去 $B_j$ 的國小的不方便度為 $|A_i - B_j|$ ，現在你要安排每個國小生要去的學校，使得所有國小生的總不方便度最低。注意在這題每個國小生都要去不同的小學。
對兩個數列排序對項絕對值差和就是答案，不過其實我好像不會證 @_@ 
#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	vector<lld> a(n), b(n);
	for (lld &ai: a) cin >> ai;
	for (lld &bi: b) cin >> bi;
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	lld ans = 0;
	for (int i = 0; i < n; ++i)
		ans += abs(a[i] - b[i]);
	cout << ans << '\n';
	return 0;
}

留言

張貼留言

這個網誌中的熱門文章

[NPSC] 2009初賽 E. 檸檬汽水傳說

題目連結: http://contest.cc.ntu.edu.tw/npsc2009/2009sen.pdf 不 本題複雜度大概要做到$O(n)$或$O(n \log n)$，所以明顯naive的枚舉點對做法是不可能會好的，不妨思考其實每個人都只要往一邊看就好了，而且當看到一個比自己大的數就可以停了，那應該可用stack做，而明顯要用stack做的話，要有一定的單調性，想想後發現遞減的是好的，每次都pop掉比自己小的人並把pop了幾個加上去，不過值得注意的是如果是pop掉跟自己一樣的人的話，記得要把他原本的size記錄下來，之後要擺回去，因為其他人都還是可以跟你做匹配之類的，此外因為每個人都還可以跟隔壁的人溝通，所以當隔壁有人時記得多加一。 #include <bits/stdc++.h> using namespace std; class knight{ private: int __val; long long __size; public: knight(int a,int b){__val=a;__size=b;} int operator++(int a){if(a==0)return __size++;} bool operator<=(int a){return __val<=a;} bool operator==(int a){return __val==a;} friend void operator+=(long long &a, knight b){a+=b.__size;} }; stack<knight> ss; int main(){ int t; scanf("%d",&t); while(t--){ int sz; long long ans=0; scanf("%d",&sz); while(!ss.empty())ss.pop(); for(int i=0;i<sz;i++){ int aaa; scanf("%d",&aaa); long long kk=1; while(!ss.empty()&
閱讀完整內容

[TIOJ] 1902. 「殿仁．王，不認識，誰啊？」，然後他就死了……

題目連結: https://tioj.infor.org/problems/1902 直接回滾莫隊後套個 trie 來查區間 xor 最大值，複雜度 $O((N^2/K + QK) \log C)$ 之類的(沒仔細算)，$K$好好挑一下就會過。 p.s. 好像好多古代人的解都是 $O(N^2 + Q)$ 😥 #include <algorithm> #include <functional> #include <iostream> #include <iterator> #include <numeric> #include <utility> #include <vector> int main() { std::cin.tie(nullptr)->sync_with_stdio(false); auto maxi = [](auto &a, auto b) { a = std::max(a, b); }; int n, q; std::cin >> n >> q; std::vector<uint32_t> a(1); std::copy_n(std::istream_iterator<int>(std::cin), n, std::back_inserter(a)); std::partial_sum(a.begin(), a.end(), a.begin(), std::bit_xor()); struct Q { int l, r, id; Q(int l_, int r_, int id_) : l(l_), r(r_), id(id_) {} }; static constexpr int K = 128; std::vector<std::vector<Q>> qs((n + K - 1) / K); for (int i = 0; i < q; ++i) { int l, r; std::cin >> l >> r; --l; qs[l / K
閱讀完整內容

[AtCoder] [經典競程 90 題] 024 - Select +／- One（★2）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_x 題目大意: 給定兩個序列 $A$, $B$，每次操作可以把$A$中任意元素$A_i$變成$A_i-1$或$A_i+1$，問可不可以恰$K$次後把$A$變成$B$。 隨手用python寫了一個XD 總之想法就是如果$A_i$比$B_i$小，那我們一定至少要花$B_i-A_i$次把$A_i$變成$B_i$，比較大的 case 也差不多，於是我們就有了一個基礎的下界$\sum |A_i-B_i|$，如果$K$比這個下界少，那一定不可能可以讓$A$跟$B$一樣。而若超過這個下界的話，實際上我們也可以透過一連串的$+1$跟$-1$操作來刻意浪費那些多出來的步數，所以再多判一下奇偶性就可以知道是不是一定可以有解了。(奇偶性一樣就可以靠前面說的方式構造，不同的話則因為我們每一步對應的奇偶性都是固定的，所以不同則一定構不出來) n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) s = 0 for i in range(n): s += abs(a[i] - b[i]) print("Yes" if s <= k and s % 2 == k % 2 else "No")
閱讀完整內容