推公式/二分法
好题！
题解：http://blog.csdn.net/zck921031/article/details/7690288
这题明显是一个方程组……可以推公式推出来……
然而这太繁琐了！发现a[i]是满足单调性的话，我们就可以二分a[1]，递推出a[n+1]，进行验证……
思维复杂度比推公式低到不知哪里去了，真是一种优秀的算法（然而我想不到，并没有什么*用……）
Source Code
Problem: User: sdfzyhy
Memory: 736K Time: 16MS
Language: G++ Result: Accepted Source Code //PKUSC 2013 B
//POJ 2601
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
const double eps=1e-;
/*******************template********************/ int n;
double a[N],c[N],ed;
inline double check(double x){
a[]=x;
F(i,,n+) a[i]=*(a[i-]+c[i-])-a[i-];
return a[n+];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
#endif
scanf("%d%lf%lf",&n,&a[],&ed);
F(i,,n) scanf("%lf",&c[i]);
double l=-,r=,mid;
while(r-l>eps){
mid=(l+r)/;
if (check(mid)>ed) r=mid;
else l=mid;
}
printf("%.2f\n",l);
return ;
}
Simple calculations
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 6646 | Accepted: 3322 |
Description
There is a sequence of n+2 elements a0, a1, ..., an+1 (n <= 3000, -1000 <= ai <=1000). It is known that ai = (ai-1 + ai+1)/2 - cifor each i=1, 2, ..., n.
You are given a0, an+1, c1, ... , cn. Write a program which calculates a1.
You are given a0, an+1, c1, ... , cn. Write a program which calculates a1.
Input
The first line of an input contains an integer n. The next two lines consist of numbers a0 and an+1 each having two digits after decimal point, and the next n lines contain numbers ci (also with two digits after decimal point), one number per line.
Output
The output file should contain a1 in the same format as a0 and an+1.
Sample Input
1
50.50
25.50
10.15
Sample Output
27.85
Source