还是太弱,很明显的一道树状数组竟然很久想不出来。这道题如果想到如何排序了,就好做了。
按题目题意,我们要找强壮的,那么就先把最强壮的找出来,存起来,然后找第二强壮的,此时已经知道比他强壮的牛有多少头了,依次类推,最后所有牛的结果都能求出来,如果从最弱的开始找,显然是无法找出来的。
然后注意一下区间重合时一定要特判。每头牛都要插入树状数组中。
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 1000000009
#define LOCA
using namespace std;
int n, b[100001], ans[100001];
struct cow
{
int s, e, id;
}p[100005];
bool cmp(cow x, cow y)
{
if(x.s == y.s) return x.e > y.e;
else return x.s < y.s;
}
int lowbit(int x)
{
return x & -x;
}
void modify(int x)
{
for(int i = x; i > 0; i -= lowbit(i))
b[i]++;
}
int sum(int x)
{
int s = 0;
for(int i = x; i < 100001; i += lowbit(i))
s += b[i];
return s;
}
int main()
{
#ifdef LOCAL
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
#endif
int i;
while(scanf("%d", &n) != EOF)
{
if(n == 0) break;
memset(b, 0, sizeof(b));
for(i = 0; i < n; i++)
{
scanf("%d%d", &p[i].s, &p[i].e);
p[i].s++;
p[i].e++;
p[i].id = i;
}
sort(p, p + n, cmp);
for(i = 0; i < n; i++)
{
if(i > 0 && p[i].s == p[i - 1].s && p[i].e == p[i - 1].e)
ans[p[i].id] = ans[p[i - 1].id];
else
{
ans[p[i].id] = sum(p[i].e);
}
modify(p[i].e);
}
for(i = 0; i < n - 1; i++)
printf("%d ", ans[i]);
printf("%d\n", ans[n - 1]);
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1744222
poj 2430 Lazy Cows.md
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
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分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
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上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。