3212.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3212  User Id:fzk 
Memory:4772K  Time:2934MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <vector>
#include <algorithm>
using namespace std;
#define __int64 long long

const int size = 100010;

__int64 s[size];
int ss[size];
int m;
int pos[100100];

//清除
void clear( )
{
	memset( s, 0, sizeof s );
	memset( ss, 0, sizeof ss );
}

inline int lowbit(int a)
{
	return a&(a^(a-1));
}

//设置a[y] = 1; 要求y>=0
void set( int y, int key )
{
	int j;

	y++;

	for(j=y;j<=m;j+=lowbit(j)) {
		s[j] += key;
		ss[j]++;
	}
}

//计算a[0,y]的和; y>=0
__int64 count(int y, int &count)
{
	__int64 ans=0;
	int j;
	y++;
	count = 0;

	for(j=y;j>0;j-=lowbit(j)) {
		ans+=s[j];
		count += ss[j];
	}

	return ans;
}

struct point {
	int x, y, id, X, Y;
}p[100000];


bool cmp( const point &a, const point &b ) {
	return a.X < b.X || a.X == b.X && a.Y > b.Y;
}

inline void rotate( point &a ) {
	int t = -a.y;
	a.y = a.x;
	a.x = t;
}

__int64 sum[100100];
int temp[100100];

int main()
{
	int n, i, k, h;
	scanf( "%d", &n );
	
	for( i=0; i<n; i++ ) {
		scanf( "%d%d", &p[i].x, &p[i].y );
		p[i].id = i;
	}

	memset( sum, 0, sizeof sum );

	for( k=0; k<4; k++ ) {
		
		for( i=0; i<n; i++ ) {
			p[i].X = p[i].x+p[i].y;
			p[i].Y = 2000001-p[i].y+p[i].x;
			temp[i] = p[i].Y;
		}

		sort( p, p+n, cmp );
		sort( temp, temp+n );
		m = std::uninitialized_copy( temp, temp+n, pos ) - pos;
		
		clear( );

		for( i=0; i<n; i++ ) {
			int y = std::lower_bound( pos, pos+m, p[i].Y ) - pos;
			sum[ p[i].id ] -= count( y, h );
			sum[ p[i].id ] += (__int64)h*p[i].x;
			set( y, p[i].x );
		}

		if( k < 3 ) {
			for( i=0; i<n; i++ )
				rotate( p[i] );
		}
	}

	__int64 best = (__int64)1000000*n;
	
	for( i=0; i<n; i++ )
		if( sum[i] < best )
			best = sum[i];
	
	printf( "%I64d\n", best );

	return 0;

}