#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 200010;
int n, m, a[N], x[N], y[N], cinema[N*3], tot = 0, k, ans[N*3];int find(int f)
{return lower_bound(cinema + 1, cinema + k + 1, f) - cinema; // 返回找到的對應(yīng)下標(biāo)
}int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> a[i]; //n個整數(shù)a1,a2…an,其中ai表示第i個科學(xué)家懂得的語言的編號。cinema[++tot] = a[i];}cin >> m;for(int i = 1; i <= m; i++){cin >> x[i];cinema[++tot] = x[i];}for(int i = 1;i <= m; i++){cin >> y[i];cinema[++tot] = y[i];}//下面步驟為離散化sort(cinema + 1, cinema + tot + 1);k = unique(cinema + 1, cinema + tot + 1) - (cinema + 1);memset(ans, 0, sizeof(ans)); // 初始化ans 為0for(int i = 1; i <=n; i++) ans[find(a[i])]++; //第i個科學(xué)家懂得的語言的編號int ans0 = 1, ans1 = 0, ans2 = 0;for(int i = 1; i <=m; i++) //從1 到 m{int ansx = ans[find(x[i])], ansy = ans[find(y[i])];if(ansx > ans1 || (ansx == ans1 && ansy > ans2)){ans0 = i;ans1 = ansx;ans2 = ansy;}}cout << ans0 <<endl;// cout << ans1 <<endl;// cout << ans2 <<endl;return 0;
}
104. 貨倉選址
在一條數(shù)軸上有 N 家商店，它們的坐標(biāo)分別為 A1~AN。
現(xiàn)在需要在數(shù)軸上建立一家貨倉，每天清晨，從貨倉到每家商店都要運送一車商品。
為了提高效率，求把貨倉建在何處，可以使得貨倉到每家商店的距離之和最小。
輸入格式 第一行輸入整數(shù)N。 第二行N個整數(shù)A1~AN。
輸出格式 輸出一個整數(shù)，表示距離之和的最小值。
數(shù)據(jù)范圍 1≤N≤100000
輸入樣例： 4 6 2 9 1
輸出樣例： 12
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;
int n, a[N];int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + n + 1); //排序int ans = 0;int zw = a[n/2 + 1];for(int i = 1; i <= n; i++)ans += abs(a[i] - zw);cout << ans <<endl;return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 100010;
int n, m, t, x[N], y[N], a[N], s[N];int main()
{cin >> n >> m >> t;for(int i = 1; i <= t; i++) cin >> x[i] >> y[i];bool row = !(t % n), col = !(t % m);if(row){if(col) cout << "both ";else cout << "row ";}else{if(col) cout << "column ";else {cout << "impossible" << endl;return 0;}}long long ans = 0;// 這里必須得long long，不然 溢出 T.Tif(row){int num = t / n;memset(a, 0, sizeof(a));for(int i = 1; i <= t; i++) a[x[i]]++;for(int i = 1; i <= n; i++) a[i] -= num; //每個人的紙牌都減去t / ns[0] = 0;//求前綴和for(int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i]; //動態(tài)規(guī)劃的思想求前綴和sort(s + 1, s + n + 1);//"轉(zhuǎn)換為貨倉選址問題"for(int i = 1; i <=n; i++) ans += abs(s[i] - s[(n + 1) >> 1] ); //求中位數(shù) s [(n+1) >> 1] 或者 s[n/2 + 1]}if(col){int num = t / m;memset(a, 0, sizeof(a));for(int i = 1; i <= t; i++) a[y[i]]++;for(int i = 1; i <= m; i++) a[i] -= num;s[0] = 0;for(int i = 1; i <= m; i++) s[i] = s[i - 1] + a[i];sort(s + 1, s + m + 1);for(int i = 1; i <= m; i++) ans += abs(s[i] - s[(m + 1) >> 1] );// for (int i = 1; i <= m / 2; i++) ans += s[m-i+1] - s[i];}cout << ans << endl;return 0;}
