Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://codeforces.com/problemset/problem/535/C
题读了好几遍才读懂。 题意是给出一个等差数列，操作严格要求从最左边不为零的连续m个数减去1，最多执行t次后问离最左边最远的位置在哪里。 有两个限制条件…一个是本身的si不能大于t，否则无法吃完。 还有一个是从sl到sr的和不能超过m*t (比赛的时候考虑的不周到。。实际上只有当r-l+1比m大的时候才是m，也就是说要取min(m,l-r+1)) 这题正解应该是二分….直接Lower_bound。。。看到也有人用前缀和搞的。 我是解方程了（貌似是个傻逼做法）…. 可以列出一个关于r的一元二次方程。。。然后求根公式2333 方程是：
然后再和第一个条件得到的r比较取小的就是结果…..
等周末把这题的二分解法也写一些。
下面是蒟蒻傻逼的数学方恒解法的代码：
1
2
3 /* ***********************************************
4 Author :111qqz
5 Created Time :2016年03月03日 星期四 13时49分13秒
6 File Name :code/cf/problem/535C.cpp
7 ************************************************ */
8
9 #include <iostream>
10 #include <algorithm>
11 #include <cstring>
12 #include <cmath>
13 #include <cstdio>
14
15 using namespace std;
16 typedef long long LL;
17 const int N=1e5+5;
18 LL A,B,n,l,t,m,p,q,k,ans,a,b,c,dd,q2;
19 long double d,pp;
20 int main()
21 {
22 cin>>A>>B>>n;
23 for ( int i = 1; i <= n ; i++ )
24 {
25 cin>>l>>t>>m;
26 if ( t<A+B*(l-1) )
27 {
28 cout<<-1<<endl;
29 continue;
30 }
31 // l = A + (l-1)*B; //wtf。。。这行代码是什么鬼...
32 p = (int) ((t-A)/B);
33 p++;
34 a=B;
35 b=(2*A-B);
36 c=-B*l*l+3*B*l-2*m*t-2*A*l+2*A-2*B;
37 d=(-b+sqrt(b*b-4*a*c))/(2*a);
38 //cout<<"a:"<<a<<endl;
39 //cout<<"b:"<<b<<endl;
40 //cout<<"c:"<<c<<endl;
41 // cout<<"d:"<<d<<endl;
42 q = int (d);
43 q2 = int((2*t-2*A+2*B-l*B)/B);
44 // cout<<"q1:"<<q<<endl;
45 // cout<<"q2:"<<q2<<endl;
46 q = min(q,q2);
47 // cout<<"p:"<<p<<endl;
48 // cout<<"q"<<q<<endl;
49 ans = min (p,q);
50 cout<<ans<<endl;
51 }
52 return 0;
53 }