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
样例输出
2
样例解释
a2=8, a3=4, a4=7之和为19，满足条件。而任何两个相邻数之和均小于18。
#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
int n,m=0,sum;
cin>>n;
int *a= new int[n];
for(int i=0;i<n;++i)
{
cin>>a[i];
m+=a[i];
}
cin>>sum;
if(m>1000000||sum>1000000||m<sum) { cout<<"Input error!"; exit(0); }
int k=0,l=n,min;
for(int i=0;i<n;++i)
{
m=0;
for(int j=0;i+j<n;++j)
{
m+=a[i+j];
if(m>=sum&&j<l-k)
{ k=i; l=i+j; }
}
}
cout<<l-k<<endl;
delete []a;
return 0;
}
3. 钉子与木板 (30分)
问题背景
墙上有n个钉子，编号为1, 2, ..., n。其中钉子i的横坐标为i，纵坐标初始为xi。可以进行两种操作：
0 k v：移动操作。竖直移动钉子k，坐标变为(k, v)。
1 s t v：测试操作。若在高度为v处放一块横坐标范围是[s,t]的水平木板，它将下落到什么高度？换句话说，求出钉子s, s+1, s+2, …, t的纵坐标中，不超过v的最大值。如果这些钉子的高度全部大于v，则木板将落到地上，高度为0。
注意，在测试操作时，水平木板只是用来测试的“临时木板”，将在测试后立即被拿走，不会影响到后续测试工作。
输入格式
第一行包含两个整数n, m，即钉子的个数和操作的个数（1<=n,m<=105）。以下n行每行一个不超过109的非负整数，即xi。以下 m 行为各操作 （1 <= k <= n, 1 <= s < t <= n, 1 <= v <= 109 ）
输出格式
按照输入的顺序，对于每个测试操作输出一个整数，即该测试水平木板的最后高度。
样例输入
5 4
1
3
5
7
9
1 2 4 6
0 3 10
1 3 5 7
1 3 5 5
样例输出
5
7
0
#include<iostream>
#include<map>
#include<cstdlib>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int a[m][4],h;
map<int,int> mp;
for(int i=0;i<n;++i)
{
cin>>h;
mp[i]=h;
}
int s,t;
for(int i=0;i<m;++i)
{
int k;
cin>>a[i][0];
if(a[i][0]==0) k=3;
else k=4;
for(int j=1;j<k;++j)
cin>>a[i][j];
}
for(int i=0;i<m;++i)
{
if(a[i][0]==1)
{
h=a[i][3];
s=a[i][1];
t=a[i][2];
int count=0;
for(int i=s-1;i<=t-1;++i)
if(mp[i]>h) ++count;
if(count==t-s+1) { cout<<0<<endl; continue; }
int max=0;
for(int i=s-1;i<=t-1;++i)
if(mp[i]<=h && mp[i]>max) max=mp[i];
cout<<max<<endl;
}
else
{
s=a[i][1];
h=a[i][2];
mp[s-1]=h;
}
}
return 0;
}
答案是答题的时候做的，也不知道能满足多少测试？（百度是以测试的组数通过多少来给分的）。
|
