「BZOJ3210」花神的浇花集会
Description
在花老师的指导下，每周4都有一个集会活动，俗称“浇水”活动。
具体浇水活动详情请见BZOJ3153
但这不是重点
花神出了好多题，每道题都有两个参考系数：代码难度和算法难度
花神为了准备浇花集会的题，必须找一道尽量适合所有人的题
现在花神知道每个人的代码能力x和算法能力y，一道题（代码难度X算法难度Y）对这个人的不适合度为 Max ( abs ( X – x ) , abs ( Y – y ) )
也就是说无论太难还是太简单都会导致题目不适合做（如果全按花神本人能力设题，绝对的全场爆0的节奏，太简单，则体现不出花神的实力）
当然不是每次都如花神所愿，不一定有一道题适合所有人，所以要使所有人的不合适度总和尽可能低
花神出了100001*100001道题，每道题的代码难度和算法难度都为0，1，2，3，……，100000
Input
第一行一个正整数N，表示花神有N个学生，花神要为这N个学生选一道题
接下来N行，每行两个空格隔开的整数x[i],y[i]，表示这个学生的代码能力和算法能力
Output
一个整数，表示最小的不合适度总和
Sample Input
3
1 2
2 1
3 3
Sample Output
3
HINT
对于100%的数据，n<=100000,0<=x[i],y[i]<=100000
题解
http://blog.sina.com.cn/s/blog_8d5d2f0401018o4y.html
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define mod 10000007 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int x[100005],y[100005]; double a[100005],b[100005]; ll mn=1e60; void solve(int kx,int ky) { ll ans=0; for(int i=1;i<=n;i++)ans+=max(abs(a[i]-kx),abs(b[i]-ky)); mn=min(mn,ans); } int main() { n=read(); for(int i=1;i<=n;i++) { a[i]=read();b[i]=read(); x[i]=a[i]*0.5+b[i]*0.5;y[i]=a[i]*0.5-b[i]*0.5; } sort(x+1,x+n+1); sort(y+1,y+n+1); int kx=x[n/2+1]+y[n/2+1],ky=x[n/2+1]-y[n/2+1]; for(int i=kx-1;i<=kx+1;i++) for(int j=ky-1;j<=ky+1;j++) solve(i,j); printf("%lld\n",mn); return 0; } |
Subscribe
计数器 9303162
OI 课件=>
OI 课件=>