题意: 一个等差数列, 首项为 a, 公差为 b, 无限长. 操作 cz 是区间里选择最多 m 个不同的非 0 元素减 1, 最多操作 t 次, 现给出区间左端 ll, 在 t 次操作能使区间全为 0 的情况下, 问右端最大为多少.
这么一个简单题吞了我 3 小时的时间. 主要是没考虑全.
首先, 得出 ll 位置的值 a1, 如果 a1>t 那么不可行.
然后分 2 种情况.
1. 区间长度 <=m, 那么只要右端 <=t 就行, 否则不行.
2. 区间长度 > m, 区间内元素总和 <=m*t, 且右端 <=t 就行, 否则不行. 这个我猜到了, 不过忽略了右端 <=t, 因此 wa 了很久.
乱码:
- //#pragma comment(linker,"/STACK:1024000000,1024000000")
- #include<iostream>
- #include<cstdio>
- #include<string>
- #include<cstring>
- #include<vector>
- #include<cmath>
- #include<queue>
- #include<stack>
- #include<map>
- #include<set>
- #include<algorithm>
- #include <stack>
- #include <list>
- using namespace std;
- const int SZ=1000010,INF=0x7FFFFFFF;
- typedef long long lon;
- int main()
- {
- std::ios::sync_with_stdio(0);
- //freopen("d:\\1.txt","r",stdin);
- lon a,b,n;
- cin>>a>>b>>n;
- for(lon i=0;i<n;++i)
- {
- lon ll,t,m;
- cin>>ll>>t>>m;
- lon lo=ll,hi=1e6+10;
- for(;lo<hi;)
- {
- lon mid=(lo+hi)/2;
- lon cur=0;
- lon a1=a+(ll-1)*b;
- lon len=(mid-ll+1);
- cur=a1*len+len*(len-1)*b/2;
- bool ok=0;
- if(len<=m)
- {
- ok=(a+(mid-1)*b)<=t;
- }
- else
- {
- ok=cur<=m*t&&(a+(mid-1)*b)<=t;
- }
- //cout<<"cur:"<<cur<<endl;
- //cout<<(m*t)<<""<<ok<<" "<<lo<<" "<<hi<<" "<<"mid: "<<mid<<" "<<cur<<endl;
- if(!ok)hi=mid;
- else lo=mid+1;
- }
- cout<<(lo-1<ll?-1:lo-1)<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2769224.html