POJ 3067 Japan

　　本題東邊有N個城市，西邊有M個城市，現在欲蓋多條高速公路連接東西邊，求路線的交點數。

ps.不會有三邊共點的情形

struct city{

     int e;  // 存東邊城市編號

     int w;  // 存西邊城市編號

}

想法1：每次讀入(e,w)時(設第k次)就檢查(k-1)次之前所有情況，若city[k-1].e<city[k].e，則city[k-1].w>city[k].w才會有交點，反之。此算法為O(n^2)會TLE。

	#include<cstdio>
	using namespace std;
	int main()
	{
	int T,t,N,M,K,k,i;
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
	int e[100000],w[100000];
	int cross=0;
	scanf("%d %d %d",&N,&M,&K);
	for(k=0;k<K;k++){
	scanf("%d %d",&e[k],&w[k]);
	for(i=0;i<k;i++){
	if(e[i]<e[k])
	if(w[i]>w[k]) cross++;
	else if(e[i]>e[k])
	if(w[i]<w[k]) cross++;
	}
	}
	printf("Test case %d: %d\n",t,cross);
	}
	return 0;
	}

view raw [POJ] 3067 Japan 1.cpp hosted with ❤ by GitHub

想法2: 可依e由小到大(若e相等則依w小到大排)將city[K]排序，此時將只討論city[k-1].e<city[k].e的情況，只要檢察前(k-1)次的w值大於第k次的w值的總和就是解答，但如果又用兩個for loop來跑又變成O(n^2)的算法，本題可簡化為求city[K]的逆序數，使用mergesort求逆序數(可參考UVa 10810)，此算法為O(nlgn)會AC。

	#include<cstdio>
	#include<algorithm>
	using namespace std;
	struct city{
	int e;
	int w;
	};
	bool cmp(city a,city b);
	void mergesort(int l,int h,city a[]);
	void combine(int l,int mid,int h,city a[]);
	long long int cross=0;
	int buffer[500001];
	int main()
	{
	int T,t,N,M,K,k,i;
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
	city a[100000]; cross=0;
	scanf("%d %d %d",&N,&M,&K);
	for(k=0;k<K;k++)
	scanf("%d %d",&a[k].e,&a[k].w);
	sort(a,a+K,cmp);
	mergesort(0,k-1,a);
	printf("Test case %d: %lld\n",t,cross);
	}
	return 0;
	}
	bool cmp(city a,city b)
	{
	if (a.e==b.e) return a.w<b.w;
	return a.e<b.e;
	}
	void mergesort(int l,int h,city a[])
	{
	if(l==h) return;
	int mid=(l+h)/2;
	mergesort(l,mid,a);
	mergesort(mid+1,h,a);
	combine(l,mid,h,a);
	}
	void combine(int l,int mid,int h,city a[])
	{
	int lcnt=l,hcnt=mid+1,bufcnt=0;
	while(lcnt<=mid && hcnt<=h){
	if(a[hcnt].w<a[lcnt].w){
	buffer[bufcnt++]=a[hcnt++].w;
	cross+=(mid-lcnt+1);
	}
	else buffer[bufcnt++]=a[lcnt++].w;
	}
	while(lcnt<=mid) buffer[bufcnt++]=a[lcnt++].w;
	while(hcnt<=h) buffer[bufcnt++]=a[hcnt++].w;
	for(bufcnt=0;l<=h;l++)
	a[l].w=buffer[bufcnt++];
	}

view raw [POJ] 3067 Japan 2.cpp hosted with ❤ by GitHub