31 条题解
-
1
他的亲野爹 LV 8 @ 2019-04-05 10:11:44
#include <stdio.h> #include <string.h> #include <math.h> //int tmp[10005]; int swap(int *a, int *b) { int tmp=*a; *a=*b; *b=tmp; return 0; } int * sort (int * data,int a,int b) { int n=b-a+1,m=a+(b-a)/2,i,j,k;// printf("enter sort %d %d \n",a,b); if(n<=2) { if(data[a]>data[b]) swap(&data[a],&data[b]); } else { sort(data, a, m); sort(data,m+1,b); j=a; k=m+1; int tmp[b+10]; /* for(i=a;i<=b;i++) { if((data[j]<data[k]||k>b)&&j<=m) { tmp[i]=data[j]; j++; } if((data[j]>=data[k]||j>m)&&k<=b) { tmp[i]=data[k]; k++; } }*/ i=a; while(j<=m&&k<=b) { if(data[j]<=data[k]) { tmp[i]=data[j]; j++; } else { tmp[i]=data[k]; k++; } i++; } if(j>m) { while(k<=b) { tmp[i]=data[k]; k++; i++; } } else if(k>b) { while(j<=m) { tmp[i]=data[j]; j++; i++; } } for(i=a;i<=b;i++) data[i]=tmp[i]; // for(i=a;i<=b;i++)printf("%d\t",tmp[i]);printf("\n"); } //for(i=a;i<=b;i++) printf("%d\t",data[i]);printf("\n"); return data; } int main() { int N,i; scanf("%d",&N); int x[N],y[N]; memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); for(i=0;i<N;i++) scanf("%d %d",&x[i],&y[i]); sort(y,0,N-1); int ans=0; for(i=0;i<N;i++) ans+=abs(y[i]-y[N/2]); //for(i=0;i<N;i++) printf("%d\n",y[i]); sort(x,0,N-1); for(i=0;i<N;i++) x[i]=x[i]-i; sort(x,0,N-1); for(i=0;i<N;i++) ans+=abs(x[i]-x[N/2]); printf("%d",ans); return 0; } -
0
评测结果 编译成功 foo.cpp: In function 'int main()': foo.cpp:13:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses] ans += abs(x[n+1>>1]-x[i])+abs(y[n+1>>1]-y[i]); ^ foo.cpp:13:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses] ans += abs(x[n+1>>1]-x[i])+abs(y[n+1>>1]-y[i]); ^ 测试数据 #0: Accepted, time = 0 ms, mem = 588 KiB, score = 10 测试数据 #1: Accepted, time = 0 ms, mem = 588 KiB, score = 10 测试数据 #2: Accepted, time = 15 ms, mem = 584 KiB, score = 10 测试数据 #3: Accepted, time = 0 ms, mem = 584 KiB, score = 10 测试数据 #4: Accepted, time = 0 ms, mem = 588 KiB, score = 10 测试数据 #5: Accepted, time = 0 ms, mem = 588 KiB, score = 10 测试数据 #6: Accepted, time = 0 ms, mem = 588 KiB, score = 10 测试数据 #7: Accepted, time = 15 ms, mem = 588 KiB, score = 10 测试数据 #8: Accepted, time = 0 ms, mem = 588 KiB, score = 10 测试数据 #9: Accepted, time = 15 ms, mem = 588 KiB, score = 10 Accepted, time = 45 ms, mem = 588 KiB, score = 100 代码 #include <algorithm> #include <cstdio> using namespace std; int n,ans = 0,x[10001],y[10001]; int main() { scanf("%d",&n); for (int i = 1;i <= n;i++) scanf("%d%d",&x[i],&y[i]); sort(x+1,x+n+1); for (int i = 1;i <= n;i++) x[i] -= i-1; sort(x+1,x+n+1); sort(y+1,y+n+1); for (int i = 1;i <= n;i++) ans += abs(x[n+1>>1]-x[i])+abs(y[n+1>>1]-y[i]); printf("%d",ans); return 0; } -
0
chenjuncong LV 7 @ 2015-08-04 14:32:31
排序或O(N)找中位数都可以，找两遍，（不在同一列是前提，可证第二遍中位数不变数据依然原序递增）
-
0
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
main()
{
int n,i,x[10001],y[10001],s1=0,s2=0;
cin>>n;
for(i=0;i<n;i++)
cin>>x[i]>>y[i];
sort(x,x+n);
sort(y,y+n);
for(i=0;i<n;i++)
x[i]-=i;
sort(x,x+n);
for(i=0;i<n;i++)
{
s1+=abs(x[i]-x[n/2]);
s2+=abs(y[i]-y[n/2]);
}
cout<<s1+s2;
} -
0
一次秒杀！
program p1440;
var a:array[1..10000] of longint;
b,c:array[-10000..10000] of longint;
x,y,x1,y1:array[1..10000] of longint;
sum,n,h:longint;
//
procedure init;
var i:longint;
begin
readln(n);
for i:=1 to n do readln(x[i],y[i]);
if odd(n) then h:=(n+1) shr 1
else h:=n shr 1;
end;
//
procedure main1;
var i:longint;
begin
for i:=1 to n do inc(b[y[i]]);
for i:=-9999 to 10000 do c[i]:=c[i-1]+b[i-1];
for i:=1 to n do
begin
inc(c[y[i]]);
y1[c[y[i]]]:=y[i];
end;
y:=y1;
for i:=1 to n do sum:=sum+abs(y[i]-y[h]);
end;
//
procedure main2;
var i:longint;
begin
fillchar(b,sizeof(b),0);fillchar(c,sizeof(c),0);
for i:=1 to n do inc(b[x[i]]);
for i:=-9999 to 10000 do c[i]:=c[i-1]+b[i-1];
for i:=1 to n do
begin
inc(c[x[i]]);
x1[c[x[i]]]:=x[i];
end;
x:=x1;
for i:=1 to n do x[i]:=x[i]-i+1;
fillchar(b,sizeof(b),0);fillchar(c,sizeof(c),0);
for i:=1 to n do inc(b[x[i]]);
for i:=-9999 to 10000 do c[i]:=c[i-1]+b[i-1];
for i:=1 to n do
begin
inc(c[x[i]]);
x1[c[x[i]]]:=x[i];
end;
x:=x1;
for i:=1 to n do sum:=sum+abs(x[i]-x[h]);
end;
//
procedure print;
begin
write(sum);
end;//
begin
init;
main1;
main2;
print;
end. -
0
编译成功
foo.pas(71,23) Warning: Comment level 2 found
foo.pas(72,23) Warning: Comment level 2 found
测试数据 #0: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #3: WrongAnswer, time = 0 ms, mem = 848 KiB, score = 0
测试数据 #4: WrongAnswer, time = 0 ms, mem = 852 KiB, score = 0
测试数据 #5: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 848 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 852 KiB, score = 10
WrongAnswer, time = 15 ms, mem = 852 KiB, score = 80
三快排整么用啊？？ -
0
w122185976 LV 10 @ 2009-07-16 15:37:52
注意:y0不一定要在yi上,如果not odd(n),而且y[n div 2]+y[n div 2+1] mod 2=0就直接用y[n div 2]+y[n div 2+1] div 2的值当中位数.
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms思路很绕，而且我用的是计数排序，毕竟x,y范围很小。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
三次快排!
他的亲野爹
LV 8
@ 2019-04-05 10:11:44
信息
- ID
- 1440
- 难度
- 5
- 分类
- 其他 | 排序 点击显示
- 标签
- 递交数
- 516
- 已通过
- 188
- 通过率
- 36%
- 被复制
- 5
- 上传者
-
caocao9926
