题意:FJ有n头牛(编号为1~n),每一头牛都有一个测验值[S, E],如果对于牛i和牛j来说,它们的测验值满足下面的条件则证明牛i比牛j强壮:Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的测验值,要求输出每头牛有几头牛比其强壮。
思路:树状数组。需要对牛i比牛j强壮的条件进行理解。把牛群按照测验值E的降序排序,(E相等按S的升序),那么接着就只需考虑S值,如果当前牛的测验值为[s, e],那么比它强壮的牛的个数,就等于排序在它前面的,S值在[0,s]区间的牛数量(E相等的话为[0,s-1])。下面的就是树状数组部分了。此外还要考虑,如果存在两头牛区间一致的情况,只需要在求和的基础上减去就行了。总体而言这道题目和star的那个题目完全类型一致。
代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
const int Max=100005;
struct data
{
int id,s,e;
}pre,cow[Max];
int n,ar[Max],maxval;
int lowbit(int i)
{
return i&(-i);
}
int max(int a,int b)
{
return a>b?a:b;
}
bool cmp(data a,data b)
{
if(a.e==b.e)
return a.s<b.s;
else
return a.e>b.e;
}
void add(int i)
{
while (i<=maxval)
{
ar[i]+=1;
i+=lowbit(i);
}
}
int sum(int i)
{
int ans=0;
while (i>0)
{
ans+=ar[i];
i-=lowbit(i);
}
return ans;
}
int main()
{
int i,s,e,ans[Max];
while (scanf("%d",&n)&&n)
{
memset(ar,0,sizeof(ar));
maxval=0;
for (i=0;i<n;i++)
{
scanf("%d%d",&s,&e);
s++,e++;//加一的目的是为了避免0的出现
cow[i].s=s;
cow[i].e=e;
cow[i].id=i;
maxval=max(maxval,cow[i].s);
}
sort(cow,cow+n,cmp);
int cnt=0;
pre.s=pre.e=-1;
for (i=0;i<n;i++)
{
if (cow[i].s==pre.s&&cow[i].e==pre.e)//如果两个牛的区间相同的处理
cnt++;
else
{
cnt=0;
pre.s=cow[i].s;
pre.e=cow[i].e;
}
ans[cow[i].id]=sum(cow[i].s)-cnt;
add(cow[i].s);
}
for (i=0;i<n;i++)
printf("%d ",ans[i]);
printf("\n");
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1744222
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
Poj中一些题目的源代码,里面共有二十多道题目,OI