poj 2761 Feed the dogs [해법 1]
Your task is to help Jiajia calculate which dog ate the food after each feeding.
Input The first line contains n and m, indicates the number of dogs and the number of feedings.
The second line contains n integers, describe the pretty value of each dog from left to right. You should notice that the dog with lower pretty value is prettier.
Each of following m lines contain three integer i,j,k, it means that Jiajia feed the k-th pretty dog in this feeding.
You can assume that n<100001 and m<50001.
Output Output file has m lines. The i-th line should contain the pretty value of the dog who got the food in the i-th feeding.
해법 2 견 [여기].분 산 된 후에 디지털 크기 에 따라 트 리 배열 을 유지 하고 질문 을 구간 별로 왼쪽 에서 오른쪽으로 정렬 한 후에 선형 스 캔 을 하여 현재 구간 안의 숫자 개 수 를 유지 한 다음 에 2 분 의 답 으로 k 가 작 으 면 됩 니 다.총 시간 복잡 도 O (nlogn + mlognlogn).
#include
#include
#include
using namespace std;
struct query
{
int l,r,k,num;
bool operator < (const query & qqq) const
{
return lq[50010];
int ori[100010],a[100010],ord[100010],m,n,nn,s[100010],ans[50010];
void inc(int x)
{
for (;x<=nn;x+=x&-x)
s[x]++;
}
void dec(int x)
{
for (;x<=nn;x+=x&-x)
s[x]--;
}
int sum(int x)
{
int ret=0;
for (;x;x-=x&-x)
ret+=s[x];
return ret;
}
int find(int k)
{
int l,r,mid,i,j,x;
l=1;
r=nn;
while (l2;
if (sum(mid)>=k) r=mid;
else l=mid+1;
}
return l;
}
int main()
{
int i,j,k,p,x,y,z;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
{
scanf("%d",&ori[i]);
ord[i]=ori[i];
}
sort(ord+1,ord+n+1);
nn=unique(ord+1,ord+n+1)-ord-1;
for (i=1;i<=n;i++)
a[i]=lower_bound(ord+1,ord+nn+1,ori[i])-ord;
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
q[i].num=i;
}
sort(q+1,q+m+1);
q[0].l=q[1].l;
q[0].r=q[1].l-1;
for (i=1;i<=m;i++)
{
for (j=q[i-1].l;j<q[i].l;j++)
dec(a[j]);
for (j=q[i-1].r+1;j<=q[i].r;j++)
inc(a[j]);
ans[q[i].num]=find(q[i].k);
}
for (i=1;i<=m;i++)
printf("%d
",ord[ans[i]]);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.