/*
最后一题比较难！
*/
solution：观察这个奇怪的图，不能共用走廊，就是1.2打包，3,4打包，每个包之间连线的线段覆盖问题。
考虑吧每个数映射成一个约为一半的数，且相邻(前奇后偶映射值一样)，如1.2映射为1且3.4映射为2，(2x-1.2x)映射成x
然后线段覆盖，用差分维护即可。
# include <bits/stdc++.h>
using namespace std;
const int MAXN=;
int s[MAXN],c[MAXN];
int n;
inline int read()
{
int X=,w=;char c=;
while (!(c>=''&&c<='')) w|=c=='-',c=getchar();
while (c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
void add(int l,int r)
{
c[l]++; c[r+]--;
}
int main()
{
n=read();
for (int i=;i<=n;i++) {
int l=(read()+)/,r=(read()+)/;
if (l>r) swap(l,r);
add(l,r);
}
for (int i=;i<=;i++) s[i]=s[i-]+c[i];
int ans=;
for (int i=;i<=;i++) ans=max(ans,s[i]);
printf("%d\n",ans*);
return ;
}
solution：可以字符串哈希、可以字典树、可以直接hash映射！
# include <bits/stdc++.h>
using namespace std;
const int N=;
char s[N],A[N];
int ans;
struct tt{
int ch[N][],size;
int val[N];
tt(){
size=;
memset(ch[],,sizeof(ch[]));
memset(val,,sizeof(val));
}
int idx(char a) { return a;}
void insert()
{
int u=,len=strlen(s);
for (int i=;i<len;i++) {
int c=idx(s[i]);
if (!ch[u][c]) {
memset(ch[size],,sizeof(ch[size]));
ch[u][c]=++size;
}
u=ch[u][c];
}
val[u]++;
if (val[u]>ans) {
ans=val[u];
memcpy(A,s,sizeof(s));
}
}
}Tree;
int main()
{
int T; scanf("%d",&T);
while (T--) {
scanf("%s",s);
Tree.insert();
}
printf("%s %d\n",A,ans);
return ;
}
solution：这道题就是最小化
可以证明，d是ai中位数时最小！
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=2e6+;
int a[N],n,o,ans;
inline int read()
{
int X=,w=;char c=;
while (!(c>=''&&c<='')) w|=c=='-',c=getchar();
while (c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
signed main()
{
n=read();
for (int i=;i<=n;i++) read(),a[i]=read();
sort(a+,a++n);
if (n&) o=a[n/+]; else o=(a[n/]+a[n/+])/;
for (int i=;i<=n;i++) ans=ans+abs(o-a[i]);
printf("%lld\n",ans);
return ;
}