O(n)暴力即可
#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const LL N=1,M=1,MOD=1; int main()
{//freopen("t.txt","r",stdin);
int c,v0,v1,a,l;
scanf("%d%d%d%d%d",&c,&v0,&v1,&a,&l);
int nv=0,nr=v0;
int ans=0;
while(nv<c)
{
nv+=v0;
ans++;
if(nv>=c){printf("%d\n",ans);return 0;}
v0+=a;
v0=min(v0,v1);
nv-=l;
nv=max(0,nv);
}
return 0;
}
B Mister B and Angle in Polygon
把正n边形放到圆内看，每个边的圆周角是相等的。剩下的，大家都懂。
做了这么多年题第一次碰到考平面几何的。。。。
#include <iostream>
int main(){
int N,A;
std::cin>>N>>A;
std::cout<<"2 1 "<<std::max(3,std::min(N,(N*A+90)/180+2))<<std::endl;
return 0;
}
又是一道BUG题 老哥走点心吧。。 略过
#include <stdio.h>
#include <algorithm>
using namespace std; int a, b, st, en; int tag(int k) {
int rlt = (k - 1) / (a + b);
if ((k - 1) % (a + b) < a) return rlt * 2 + 1;
return rlt * 2 + 2;
} int solve(int st, int en) {
int u = tag(st), v = tag(en);
if (v > u + 4) return max(a + 1, 2 * a - b);
if (v == u) return u & 1 ? en - st + 1 : 1;
if (v == u + 1) return u & 1 ? a - ((st - 1) % (a + b)) : ((en - 1) % (a + b)) + 2;
if (v == u + 2) {
int x = a - ((st - 1) % (a + b)), y = (en - 1) % (a + b) + 1;
return u & 1 ? max(min(x + y, a), max(x, y + min(x, a - b))) : a + 1;
}
return max(solve(a * (tag(st) & 1) + 1 + (a + b) * (tag(st) >> 1), en), solve(st, (a + b) * ((tag(en) - 1) >> 1) + a * ((tag(en) - 1) & 1)));
} int main() {
scanf("%d %d %d %d", &a, &b, &st, &en);
printf("%d\n", solve(st, en));
return 0;
}
考虑对于每一个数可以预知在右移某些步数的范围内使答案变好，其余范围使答案不变或者变差，于是可以用线段树维护，然后求和。
但是n有100w 时限只有2s O（nlogn）可能超时 应该有O（n）的算法。
由于在询问之前给出了所有数值信息，即不需动态维护线段。
所以用线段树是大材小用了，直接维护即可。复杂度O（n）注意边界情况要特殊判断。
#include <bits/stdc++.h> using namespace std; int n, ta, tb, md;
long long mi = LLONG_MAX, cur, cs, dx[2000005], add[2000005]; int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &ta);
cur += abs(ta - i);
dx[(ta - i + n) % n] += 2;
dx[(1 - i + n) % n] -= 2;
add[n-i] += abs(ta - 1) - (abs(ta - n) + 1);
if ((1 - i + n) % n <= (ta - i + n) % n)
cs++;
else
cs--;
}
for (int i = 0; i < n; i++) {
if (cur < mi)
mi = cur, md = i;
cs += dx[i];
cur += cs + add[i];
}
printf("%lld %d\n", mi, md);
return 0;
}