hdu 4791 장사 현장 경기 A 문제
사고: 장수 가 있 는 구간 을 찾 으 려 면 가장 큰 비용 은 이 구간 의 가격 * 장수 입 니 다. 여분의 장 수 를 인쇄 하려 면 뒤의 구간 에서 찾 으 세 요. 뒤쪽 구간 은 모두 장수 가 목표 장수 보다 많 기 때문에 구간 의 최소 치 는 가격 이 비 증가 하고 장 수 는 증가 하 므 로 구간 의 장수 * 가격 의 최소 치 를 찾 아야 합 니 다.선분 나무 로...
다 쓰 고 나 서 야 사실 이렇게 복잡 하지 않다 는 것 을 생각 했다. 바로 뒤에서 각 구간 의 오른쪽 최소 치 를 구하 고 기록 해서 바로 사용 하면 된다.
#include<stdio.h>
#include<string.h>
const int N=100100;
__int64 cnt[N],num[N];
int n;
struct Tree
{
int L,R;
__int64 mw;
}T[N*4];
__int64 min(__int64 a,__int64 b)
{
if(a>b)return b;
return a;
}
void buildTree(int L,int R,int id)
{
T[id].L=L;T[id].R=R;
if(L==R)
{
T[id].mw=cnt[L]*num[L];
return ;
}
int li,ri,mid;
mid=(L+R)>>1;
li=id<<1;ri=li|1;
buildTree(L,mid,li);
buildTree(mid+1,R,ri);
T[id].mw=min(T[li].mw,T[ri].mw);
}
__int64 find(int L,int R,int id)
{
if(T[id].L==L&&T[id].R==R)
return T[id].mw;
int li=id<<1,ri=li|1,mid=(T[id].L+T[id].R)>>1;
if(R<=mid)return find(L,R,li);
else if(L>mid) return find(L,R,ri);
else return min(find(L,mid,li),find(mid+1,R,ri));
}
int findnum(__int64 w)
{
int L,R,mid,flag;
L=1;R=n;flag=1;
while(L<=R)
{
mid=(L+R)>>1;
if(num[mid]<=w)
{
flag=mid;
L=mid+1;
}
else R=mid-1;
}
return flag;
}
int main()
{
int i,j,m,t;
__int64 sum,w;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%I64d%I64d",&num[i],&cnt[i]);
buildTree(1,n,1);
while(m--)
{
scanf("%I64d",&w);
j=findnum(w);
if(j==n){printf("%I64d
",cnt[j]*w);continue;}
sum=find(j+1,n,1);
printf("%I64d
",min(sum,cnt[j]*w));
}
}
return 0;
}
#include<stdio.h>
#include<string.h>
const int N=100005;
__int64 cnt[N],num[N],minw[N];
int n;
__int64 min(__int64 a,__int64 b)
{
if(a>b)return b;
return a;
}
int findnum(__int64 w)
{
int L,R,mid,flag;
L=1;R=n;flag=1;
while(L<=R)
{
mid=(L+R)>>1;
if(num[mid]<=w)
{
flag=mid;
L=mid+1;
}
else R=mid-1;
}
return flag;
}
int main()
{
int i,j,m,t;
__int64 w;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%I64d%I64d",&num[i],&cnt[i]);
minw[n]=num[n]*cnt[n];
for(i=n;i>=2;i--)
{
minw[i-1]=minw[i];
if(num[i]*cnt[i]<minw[i])
minw[i-1]=num[i]*cnt[i];
}
while(m--)
{
scanf("%I64d",&w);
j=findnum(w);
if(j==n){printf("%I64d
",cnt[j]*w);continue;}
printf("%I64d
",min(cnt[j]*w,minw[j+1]));
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.