首页 > 代码库 > Ural 1010. Discrete Function
Ural 1010. Discrete Function
1010. Discrete Function
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
There is a discrete function. It is specified for integer arguments from 1 to N (2 ≤ N≤ 100000). Each value of the function is longint (signed long in C++). You have to find such two points of the function for which all points between them are below than straight line connecting them and inclination of this straight line is the largest.
Input
There is an N in the first line. Than N lines follow with the values of the function for the arguments 1, 2, …, N respectively.
Output
A pair of integers, which are abscissas of the desired points, should be written into one line of output. The first number must be less then the second one. If it is any ambiguity your program should write the pair with the smallest first number.
Sample
| input | output |
|---|---|
3264 | 1 2 |
Problem Source: Third Open USTU Collegiate Programming Contest (PhysTech Cup), March 18, 2000
来源： <http://acm.timus.ru/problem.aspx?space=1&num=1010>
?存在一个离散函数，已知定义域为 1 到 N 的整数点，对应函数值在输入中。在图像上找到两个点，使得在它们之间的点都在两点连成直线的下方，且直线的倾斜角最大。
实际上，如果这样的直线下方还有点的话，则必存在下方的点与原直线右端点连成的新直线斜率更大。所以，遍历相邻的两个点差值即可，可以直接在读取输入时就求出。
可能我没懂题意，不明白为什么设 long 会WA，设double或long long才A。
#include <stdio.h>#include <math.h>double a[100002];int main(){
long n, i, j;
double k=0;
scanf("%ld", &n);
for (i = 0; i < n; i++)
scanf("%lf", &a[i]);
for (i = 1; i < n; i++) {
if (k < fabs(a[i] - a[i-1])) {
k = fabs(a[i]- a[i-1]);
j = i;
}
}
printf("%ld %ld\n", j, j+1);
return 0;}
By Black Storm（使用为知笔记）
Ural 1010. Discrete Function
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。