中位数的和
(number.pas/c/cpp)
【题目描述】
flower 有 N-1 个朋友，他们要一起玩一个游戏：首先确定三个非负整数 a,b,c,然后每个人依次在纸上写一个数，设第 i 个人写下的数字为 f[i],flower 先写下数字 f[1]=1，对于第 i 个写数字的人(i>1)有： f[i]=(a*m[i-1]+b*i+c)mod1,000,000,007；其中 m[i-1]为前 i-1 个写下的数字的中位数，如果 i-1 为偶数，那么取靠前的那个数。flower 想要知道，所有人写下的数字的和。
【输入格式】
输入仅一行,包含四个非负整数 a,b,c,N；意义如上；
【输出格式】
输出只有一行一个整数，表示数字和。
【输入样例】
3 1 2 6
【输出样例】
103
【数据规模】
对于 30%的数据： N≤1,000；
对于 100%的数据： N≤200,000； a,b,c≤1,000,000,007。
第一次拿到这道题，给我的感觉是F[1~i-1]一定比F[i]小，所以中位数一定是F[i>>1]（CJJDs也是这样想的）,但马上被我否认了，因为我注意到有一个mod，所以值可能会变小。于是立马换一种思路，既然叫我们求中位数，即中间的数，那么我们将已存的有序数列掰成两半，中间的即为中位数。那么这里就需要用到一个大根堆，用于存储前半段数，一个小根堆，用于存储后半段数。每次将生成的数放入小根堆，如果当前是第i次操作且i为奇数，那么将小根堆顶放入大根堆。注意mod后如果小于大根堆顶就交换。
code：
#include <cstdio>
#include <cctype>
#include <queue>
#define mod 1000000007
#define C c = tc ( )
using namespace std; inline char tc(){
static char fl[],*A,*B;
return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;
} inline void read(long long &x){
static char c;
while(!isdigit(C));x=c-'';
while(isdigit(C))x=x*+c-'';
} long long a,b,c,n;
long long f[];
priority_queue<long long>w1;
priority_queue<long long,vector<long long>,greater<long long> >w2; int main(){ freopen("number.in","r",stdin);
freopen("number.out","w",stdout); read(a),read(b),read(c),read(n);
w1.push(f[]=);
for(int i=;i<=n;i++){
long long val=w1.top(),ve;
f[i]=(val*a+b*i+c)%mod;ve=f[i];
if(ve<val)w1.pop(),w1.push(ve),ve=val;
w2.push(ve);
if(i&)val=w2.top(),w2.pop(),w1.push(val);
}
long long ans=;
for(int i=;i<=n;i++)ans+=f[i];
printf("%lld",ans); fclose(stdin),fclose(stdout);
return ;
}
最后引用CJJ的话。
如果是Pascal的话我也可以，用Pascal打堆！