三分，好妙啊，我之前完全没想到
by wawcac @ 2017-07-01 23:33:37
...
by huxulin @ 2017-07-02 07:54:35
三分初值小了，wa了3个点>\_<比赛时和暴力一个分
by s_a_b_e_r @ 2017-07-02 08:06:27
我的三分好像有点误差,要在答案一定范围内暴力扫一下
by huxulin @ 2017-07-02 09:26:17
写的时候注意到了,但是不清楚具体什么原因
by huxulin @ 2017-07-02 09:30:14
@[huxulin](/space/show?uid=20115) 题解有一个三分，应该是你范围没处理好
by BlueArc @ 2017-07-02 13:10:27
```cpp
for(ll i=l-10;i<=r+10;i++){
ans=min(ans,pd(i));
}
```
它的好像也有
by huxulin @ 2017-07-02 14:06:31
范围不是0-L吗
by huxulin @ 2017-07-02 14:07:41
附上代码:
```cpp
#include <cstdio>
#include <algorithm>
typedef long long LL;
static const int maxm = 2e6 + 10;
static const LL INF = 1LL << 62;
LL r[maxm],x[maxm],A[maxm];
LL L,ans,mind = INF;
LL n;
LL abs(LL x){
return x > 0 ? x : -x;
}
LL f(LL D){
LL ret = 0;
for(LL i = 1;i <= n;i++) ret += abs(D * r[i] - x[i] * r[i]);
return ret;
}
int main(){
scanf("%lld%lld",&L,&n);
for(LL i = 1;i <= n;i++) scanf("%lld%lld",&x[i],&r[i]);
LL l = 0,r = L;
while(l <= r){
LL mid = (l + r) >> 1;
LL mmid = (mid + r) >> 1;
if(f(mid) < f(mmid)) ans = mid,r = mmid - 1;
else ans = mmid,l = mid + 1;
}
for(LL i = ans - 100;i <= ans + 100;i++)
mind = std :: min(f(i),mind);
printf("%lld\n",mind);
return 0;
}
```
by huxulin @ 2017-07-02 14:09:19
@[七芯海棠](/space/show?uid=27114)
by huxulin @ 2017-07-02 14:24:15