51nod 1414 冰雕 思路:暴力模拟题

51nod 1414 冰雕 思路:暴力模拟题

题意是现在有n个雕像把一个圆等分了,每一个雕像有一个吸引力。

叫你不移动雕像只去掉雕像让剩下的雕像还能等分这个圆,求剩下的雕像的吸引力之和的最大值。

显然去掉后剩下雕像的间隔应该是n的因子,因为这样才能使剩下的雕像等分圆。

这道题数据量不大,可以暴力枚举,模拟出每一种情况取最大值就可以了。

现在我们分析完这道题了,写一下步骤。

1.求出n的因子存在list中。

for(int i = ;i <= n/; i++){ if(n% i == ) l.push_back(i); }

2.遍历因子(因子是可以去取的间隔),遍历从1到因子作为第一个取的雕像(因为是一个圆,间隔相等有多种情况)。

  现在第一个雕像和间隔都确定了,只需要求和更新答案就好了。

    int ans = -*;
int sum;
for(it = l.begin(); it != l.end(); it++){
for(int j = ;j <= *it; j++ ){
sum = ;
for(int i = j;i <= n; i += *it){
sum += a[i];
}
ans = max(ans,sum);
}
}
cout << ans << endl;

加点注释,上上代码

#include <bits\stdc++.h>
using namespace std; int a[];
list <int> l; // 用来存 n的因子
list <int>::iterator it;
int main(){
int n;
cin >> n;
//求n的因子, n/3是题目要求不能少于3个
for(int i = ;i <= n/; i++){
if(n% i == ) l.push_back(i);
}
// for(it = l.begin();it != l.end(); it++){
// cout << *it << " " << endl;
// }
for(int i = ;i <= n; i++){
cin >> a[i];
} int ans = -*; //可能的最小值。
int sum; //对某一种情况求和 //遍历因子,即为间隔
for(it = l.begin(); it != l.end(); it++){
//遍历确定第一个雕像的位置,不清楚的话画个图。
for(int j = ;j <= *it; j++ ){
sum = ;
//求和
for(int i = j;i <= n; i += *it){
sum += a[i];
}
//更新答案
ans = max(ans,sum);
}
}
cout << ans << endl;
return ;
}
上一篇:虚拟机 VirtualBox 自制帮助文档


下一篇:使用Linux命令行测试网速