08年百度之星程序设计大赛的一题

来源：百度知道 编辑：UC知道 时间：2024/05/20 02:27:33
1. 广告排名区间 (10分)
问题背景
shifen广告消费预估系统可以估计出一段时间内一个特定的广告在检索结果中排在各个位
置的几率。比如系统对某广告的输出如下：

p1 = 0.03, p2 = 0.08, p3 = 0.04 ……

这说明该广告展现在第1位的概率是 3%，展现在第2位的概率是 8%，展现在第3位的概率是
4%……

问题是：如何给出一个排名估计区间[i, j]，使得广告出现在该区间中的概率大于或等于
一个预设值p，同时这个区间所包含的元素尽可能的少。也可用数学语言来描述：给定数p
和数列 p1, p2, … , pn，求 i和 j (1 <= i <= j <= n)，在满足pi + pi+1 + … + pj
>= p的前提下让j-i 最小。

一般来说，pi只需保留6位小数就足够了。这样，若令ai=106pi，a=106p，则a和所有的ai
均为[0,106]之间的整数。这样就避免了对实数的处理。

输入格式
第一行包含一个整数n (1 <= n <= 100,000)。
以下n行每行包含一个[0,106]内的整数，依次为a1，a2，…，an。这n个整数之和保证不超
过106。
最后一行包含一个[0,106]内的整数a。保证所有ai之和不小于a。

输出格式
输出仅一行，包含一个整数，即j – i的最小值。

样例输入
7
5
8
4
7
10
5
2
18

样例输出

谁有这一题的代码的,因为课程需要,不要和网上的代码重复最好
发我邮箱 zhuhui20062@126.com
完事之后定重谢

接分。。。

AC了的代码。。。

#include <stdio.h>
#include <string.h>

#define N 100005
int A[ N ];
int n;
int P;

void input()
{
int i;

A[ 0 ] = 0;
for ( i = 1; i <= n; ++i ) scanf( "%d", A + i );
}

void solve()
{
int i, j;
int ans;
long long sum;

ans = 10000000;
i = 1, j = 1;
sum = 0;
while ( i <= n ) {
while ( i <= n ) {
sum += A[i];
if ( sum >= P ) break;
++i;
}

while ( sum - A[j] >= P ) {
sum -= A[j];
++j;
}
if ( i - j < ans ) ans = i - j;
++i;
}

printf( "%d\n", ans );
}

int main()
{
scanf("%d", &n );
input();
scanf(" %d", &P );
if ( P == 0 ) printf( "0\n"