51NOD 1711 평균 수
길이 가 n 인 서열 a 가 있 는데 모든 구간 의 평균 수 중 k 번 째 로 크다.
첫 눈
뭐야?!!
이분
2 점 답 ans 를 생각해 볼 수 있 습 니 다. 즉, 평균 수가 ans 보다 많은 구간 의 개수 가 얼마나 되 는 지 를 요구 하 는 것 입 니 다.
평균 수가 ans 보다 큰 구간 개 수 를 구하 다.
먼저 수학 식 으로 전환: sumi - sumji - j ≥ ans 그러면 식 은 다시 sumi - sumj ≥ ans 로 전환 할 수 있다.×(i−j) ∴sumi−sumj≥ans×i−ans×j ∴sumi−ans×i≥sumj−ans×j 그러면 양쪽 모두 i 와 j 만 관련 되 기 때문에 우 리 는 모든 sumi - ans 를×i. 분 산 된 다음 에 나무 모양 의 배열 로 통계 하면 됩 니 다.
내 가 문 제 를 풀 때 처음에 0 도 넣 지 않 았 는데 틀 렸 잖 아. 그리고 2 분 범위 도 적당히 넓 어야 돼. 그리고 eps 도 있어 야 돼.
제목 링크:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1711
코드 붙 이기:
#include
#include
#include
#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long LL;
typedef double db;
const int N = 100010;
const db eps = 1e-5;
LL a[N],k;
int num[N],level[N];
db v[N];
int n;
db l,r,mid,ans;
int tree[N];
bool cmp(int x,int y){
return v[x]int get_t(int x){
int tot=0;
while(x){
tot+=tree[x];
x-=x&-x;
}
return tot;
}
void add(int x){
while(x<=n){
tree[x]++;
x+=x&-x;
}
}
LL gettot(db x){
fo(i,1,n)v[i]=db(a[i])-x*i;
sort(num,num+1+n,cmp);
int u=0;
fo(i,0,n){
if (i==0||v[num[i]]-v[num[i-1]]>eps)u++;
level[num[i]]=u;
}
fo(i,1,n)tree[i]=0;
LL tot=0;
add(level[0]);
fo(i,1,n){
tot+=get_t(level[i]);
add(level[i]);
}
return tot;
}
int main(){
freopen("average.in","r",stdin);
freopen("average.out","w",stdout);
scanf("%d%lld",&n,&k);
fo(i,1,n)scanf("%lld",&a[i]);
fo(i,1,n){
a[i]+=a[i-1];
num[i]=i;
}
l=0,r=100001,ans=0;
while(l+eps<=r){
mid=(l+r)/2;
if (gettot(mid)>=k)l=mid+eps;
else{
r=mid-eps;
ans=mid;
}
}
printf("%.4lf
",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
바 이 두 의 별 2015 첫 경기 (1) 1003 시퀀스 변환우 리 는 서열 A 에서 서열 B 로 변환 하 는 대 가 를 cost (A, B) = max (| Ai − Bi |) (1 ≤ i ≤ N) 로 정의 합 니 다. 각 조: 첫 번 째 행위 서열 A 의 길이 N (1 ≤...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.