星际网络( 数学\(\star\star \))
- 时限:\(1s\) 内存:\(256M\)
Descrption
- \(LY\) 星系有很多个星球。它们之间通过一个巨大的互联网进行通讯。随着信息时代的发展,旧的网络已经不能满足需求,于是 \(LY\) 星系决定建设一个新的网络。
- \(LY\) 星系有很多个星球,有些星球一天有几十个小时,有些星球一天只有几个小时。但每个星球的一个小时都是一样长的。因此每个星球一天的长短都不一样,这就导致了一个问题:星球上的生物都是在白天工作夜晚 休息,因此每个星球每天都有上网高峰期和低峰期,当很多星球同时达到高峰期时,网络便会变得异常拥堵,进而带来延迟。所以 \(LY\) 星系需要建设一个有足够大带宽的网络来避免这一问题。现在他们想知道,网络在一个小时内的最大流量是多少。
Input
- 输入数据的第一行为一个正整数 \(N\),表示 \(LY\) 星系共有 \(N\) 个星球。
- 接下来 \(N\) 行,每行描述一个星球。对于每个星球的描述,开头为两个正整数 \(D,T\),表示这个星球一天有 \(D\) 个小时,当前位于 \(T\) 时刻(即某一天已经过去了 \(T\) 小时).
- 接下来是 \(D\) 个正整数 \(q_0,q_1……q_{D-1}\),其中 \(q_i\) 表示第 \(i\) 小时到第 \(i+1\) 小时的流量。
Output
- 输出共一行,为一个整数 \(Ans\),表示一个小时内的最大流量。
Sample Input
2
4 0 1 2 3 4
2 0 3 1
Sample Output
6
Hint
- 在 \(4n+3\) 时刻,流量\(=3+3=6\) 达到最大。
- 对于 \(10\%\) 的数据,\(N<=10\);
- 对于 \(20\%\) 的数据,\(N<=100\);
- 对于 \(40\%\) 的数据,\(N<=10000\);
- 对于 \(70\%\) 的数据,\(N<=50000\);
- 对于全部的数据,\(N<=100000,0<=T<D<=24,q_i<=1000000\);
- 来源:
分析
- 首先观察到算法时间复杂度与 \(n\) 无关,因为一天的长度相同的星球都可以合并,至多 \(24\)个。
- 若 \(A,B\) 星球的小时数互质,则 \(A\) 星球每个时刻与 \(B\) 星球每个时刻均有机会重合。也就是说,若 \(A\) 星球的小时数与 \(1\sim 24\) 其他数都互质,则无论其他数字如何选择,这个星球都可以取到它的最大流量。\(13,17,19,23\) 满足这个条件。其他数字暴力枚举到它们的最小公倍数即可。
Code
#include <bits/stdc++.h>
typedef long long LL;
const int MAX = 55440;//除了13,17,19,23外其他数的最下公倍数
int n,tmp[30];
LL ans,psum,sum[30][30];
void Calc(int D){//计算一天的最大流量
LL Max = 0;
for(int i = 1; i <= D; ++i)Max = std::max(Max,sum[D][i]);
psum += Max;
}
void Solve(){
scanf("%d",&n);
for(int i = 1; i <= n; ++i){//n个星球D相同的合并,最多就剩下24个星球
int D,T;scanf("%d%d",&D,&T);
for(int j = 1; j <= D; ++j)scanf("%d",&tmp[j]);
for(int st = T + 1,t = 1; t <= D; ++st,++t){//时刻同步,时刻从1开始
if(st > D)st -= D;//T+1(平移了一位)都对应t=1时刻,其他依次后倒
sum[D][t] += tmp[st];//合并到一起
}
}
Calc(13);Calc(17);Calc(19);Calc(23);
for(int i = 1; i <= MAX; ++i){//大于MAX的就重复的循环了
LL cursum = 0;
for(int j = 1; j <= 24; ++j){//枚举24个合并的星球
if(j == 13 || j == 17 || j == 19 || j == 23)continue;
int cur = (i - 1) % j + 1;//计算时刻
cursum += sum[j][cur];
}
ans = std::max(ans,cursum);
}
printf("%lld\n",ans + psum);
}
int main(){
Solve();
return 0;
}
原文链接: https://www.cnblogs.com/hbhszxyb/p/13334982.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
![星际网络](https://www.ccppcoding.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/368026
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!