BZOJ 4952 [Wf 2017] 2 점 짜 리 문제 풀이 보고서

4952: [Wf2017]Need for Speed
Description
Sheila 는 학생 입 니 다. 그녀 는 전형 적 인 학생 차 를 몰 고 있 습 니 다. 늙 고 느 리 며 녹 슬 고 항상 무 너 지 는 차 입 니 다.최근 에는 시속 다이얼 의 지침 이 떨 어 졌 다.그녀 는 지침 을 붙 였 지만 각도 가 맞지 않 았 을 것 이다.따라서 디스크 의 눈금 이 s 일 때 그녀의 실제 속 도 는 s + c 일 수 있 습 니 다. 그 중에서 c 는 알 수 없 는 상수 (마이너스 일 수 있 습 니 다) 입 니 다.Sheila 는 최근 스케줄 에서 자세하게 기록 을 했 고 이 기록 으로 c 의 값 을 계산 할 수 있 기 를 희망 했다.여정 은 n 단 으로 이 루어 져 있다.i 단 에서 그녀 는 di 의 거 리 를 고 르 게 주 행 했 고 시계 판 에 대응 하 는 눈금 은 si 였 다.전체 여정 에 걸 리 는 시간 은 t 이다.Sheila 를 도와 c 의 값 을 확인 해 주세요.Sheila 의 시계 판 에 마이너스 눈금 이 있 더 라 도 그녀 는 모든 여정 의 실제 속도 가 0 보다 크다 는 것 을 주의 하 세 요.
Input
첫 번 째 줄 은 두 개의 정수 n (1 ≤ n ≤ 1000) 과 t (1 ≤ t ≤ 10 ^ 6) 를 포함 하고 각각 Sheila 의 여정 단수 와 총 시간 을 나타 낸다.다음 n 줄 은 각 줄 마다 Sheila 의 일정 을 묘사 했다.i 줄 은 두 개의 정수 di (1 ≤ di ≤ 1000) 와 si (| si | ≤ 1000) 를 포함 하고 각각 i 단 여정 의 거리 와 표 판 읽 기 수 를 나타 낸다.시간 단 위 는 시간 이 고, 단 위 는 마일 이 며, 속도 단 위 는 시간 당 마일 이다.
Output
출력 상수 c, 그 단 위 는 마일 매 시간 이다.당신 의 답안 은 절대 또는 상대 적 인 오차 가 10 ^ - 6 보다 작 아야 합 니 다.
Sample Input
샘플 1 3 5 4 - 1 4 0 10 3 샘플 2 4 10 5 3 2 3 6 3 1
Sample Output
샘플 1 3.00000000 샘플 2 - 0.50865337
[문제 풀이 보고서] 월 드 파이 널 의 문제 일 수도 있 는데...본질 적 으로 하나의 방정식 (i = 1 − n) di / (si + c) = T 구 c 를 제시 하 는 것 이다.바로 2 점 답 을 주시 면 됩 니 다. 폭력 check.
코드 는 다음 과 같 습 니 다:

/**************************************************************
    Problem: 4952
    User: onepointo
    Language: C++
    Result: Accepted
    Time:28 ms
    Memory:836 kb
****************************************************************/

#include
#include
#include
using namespace std;
#define N 1010
#define eps 1e-8
#define inf 2000000

int n;
double t,d[N],s[N];

bool check(double mid)
{
    double ans=0;
    for(int i=1;i<=n;++i)
    {
        double tmp=s[i]+mid;
        if(tmp<=0) return 1;
        ans+=d[i]/tmp;
    }
    return ans>=t;
}
int main()
{
    scanf("%d%lf",&n,&t);
    for(int i=1;i<=n;++i) scanf("%lf%lf",&d[i],&s[i]);
    double l=-inf,r=inf,mid;
    while(r-l>eps)
    {
        mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.9lf
",l);
    return 0;
}