给定一串数列， 求区间最大平均值
显然，最大的区间平均值可以就是数列中最大的那个，然后基于最大的点想两边枚举区间长度
#include <cstdio>
#include <algorithm>
inline int Max(int a, int b){return a > b? a: b;}
const int N = 1e5 + 1e4;
int n, max, max_id, len, rig, max_len;
int a[N];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
if(a[i] > max)
max = a[i];
}
for(int i = 1; i <= n; i++){
if(a[i] == max && ( a[i - 1] != max || i == 1 ) ){
rig = i; len = 0;
while( a[rig] == a[i] && rig <= n ){
rig++; len++;
}
max_len = Max(len, max_len);
}
}
printf("%d", max_len);
}B. Emotes
总共 $n$ 个表情， 你需要输出一个长度为 $m$ 的长度序列，但是同一个表情不能连续出现 $k$ 次
排个序，每个周期按，最大的出现 $k$ 次，然后出现一次第二大的，枚举周期即可
#include <cstdio>
#include <algorithm>
const int N = 2e5 + 1e4;
int n, m, k, tmp;
long long ans;
int a[N];
bool cmp(int a, int b){
return a > b;
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
std::sort(a + 1, a + n + 1, cmp);
if( m <= k ){
printf("%lld", 1LL * a[1] * m);
return 0;
}
else {
ans = 1LL * a[1] * k + (long long) a[2];
ans *= (m / (k + 1) );
m %= (k + 1);
ans += 1LL * a[1] * m;
printf("%lld", ans);
}
}C. Magic Ship
本来是到直接两点坐标差的绝对值之和就可以的
然后有洋流
我们设每一轮洋流为一个周期，然后二分最少需要多少周期
然后 $O(n)$ 判断不在整数周期内部的就可以
#include <cstdio>
inline long long Aabs(long long a){return a < 0? (0 - a): a;}
const long long N = 1e5 + 1e4;
long long x1, y1, x2, y2, dx, dy, n, tmp, ans, mid;
char str[N];
int main(){
scanf("%lld%lld", &x1, &y1);
scanf("%lld%lld", &x2, &y2);
scanf("%lld", &n);
scanf("%s", str + 1);
for(long long i = 1; i <= n; i++){
if(str[i] == 'U') dy++;
if(str[i] == 'D') dy--;
if(str[i] == 'L') dx--;
if(str[i] == 'R') dx++;
}
long long left = 0, rig = (int)2e9;
while(left <= rig){
mid = (left + rig) >> 1;
if( Aabs(x1 + dx * mid - x2) + Aabs(y1 + dy * mid - y2) <= n * mid ) rig = mid - 1;
else left = mid + 1;
}
x1 += dx * rig;
y1 += dy * rig;
ans = n * rig;
if( Aabs(x1 - x2) + Aabs(y1 - y2) <= ans){
printf("%lld", ans);
return 0;
}
for(long long i = 1; i <= n; i++){
if(str[i] == 'U') y1++;
if(str[i] == 'D') y1--;
if(str[i] == 'L') x1--;
if(str[i] == 'R') x1++;
ans++;
if( Aabs(x1 - x2) + Aabs(y1 - y2) <= ans ){
printf("%lld", ans);
return 0;
}
}
printf("-1");
}