Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:为什么二分会wa....

Posted by veasonapple at 2015-09-11 21:40:01 on Problem 2481
In Reply To:为什么二分会wa.... Posted by:veasonapple at 2015-09-11 21:38:40
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<utility>
#define mod 1000000007
using namespace std;
int n, l, r, mid;
int ans[100010];
struct Cow
{
	int s, e, id;
	friend bool operator<(Cow a, Cow b);
}cow[100010];
bool operator<(Cow a, Cow b)
{
	if (a.s > b.s)
	{
		return true;
	}
	else
	{
		if (a.s == b.s&&a.e<b.e)
		{
			return true;
		}
	}
	return false;
}
int main()
{
	while (cin >> n&&n)
	{
		for (int i = 1; i <= n; i++)
		{
			scanf("%d%d", &cow[i].s, &cow[i].e);
			cow[i].id = i;
		}
		sort(cow + 1, cow + n + 1);
		for (int i = 1; i <= n; i++)
		{
			l = i, r = n;
			while (l != r)
			{
				mid = (l + r) >> 1;
				if (cow[mid + 1].e > cow[i].e || (cow[mid + 1].e == cow[i].e&&cow[mid + 1].s < cow[i].s))
				{
					l = mid + 1;
				}
				else
				{
					r = mid;
				}
			}
			ans[cow[i].id] = l - i;
		}
		for (int i = 1; i < n; i++)
		{
			printf("%d ", ans[i]);
		}
		printf("%d\n", ans[n]);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator