学步园

  #include <iostream><br /> #include <numeric><br /> #include <vector><br /> #include <cmath><br /> using namespace std;</p> <p>const int PN = 10000000;<br /> int primes[PN];<br /> vector<int> primelist;</p> <p>void sieve() {<br /> primes[0] = 0;<br /> primes[1] = 0;<br /> primes[2] = 1;<br /> for (int i = 3; i < PN; ++i)<br /> primes[i] = i % 2;</p> <p> for (int i = 3; i <= int(sqrt(PN*1.0) + 0.5); i += 2)<br /> if (primes[i])<br /> for (int j = 2*i; j < PN; j += i)<br /> primes[j] = 0;</p> <p> for (int i = 0; i < PN; ++i)<br /> if (primes[i])<br /> primelist.push_back(i);<br /> }<br /> //这个函数的目的是生成素数表,并把素数表添加到Primelist中</p> <p>void sum(int n, vector<int>& out) {<br /> if (primelist.size() < n) return;<br /> int cursum = accumulate(primelist.begin(), primelist.begin() + n, 0);<br /> out.push_back(cursum);<br /> for (int l = 0, r = n; r < primelist.size(); ++r, ++l) {<br /> cursum += primelist[r] - primelist[l];<br /> out.push_back(cursum);<br /> }<br /> }<br /> //把所有的n个连续素数的和保存到out中</p> <p>int main()<br /> {<br /> sieve();<br /> vector<int> sums[12];<br /> sums[0] = primelist;</p> <p> //copy(primelist.begin(), primelist.begin() + 20, ostream_iterator<int>(cout, " "));</p> <p> int N; cin >> N;<br /> for (int I = 1; I <= N; ++I)<br /> {<br /> int m; cin >> m;<br /> for (int i = 1; i <= m; ++i)<br /> {<br /> int tmp; cin >> tmp;<br /> sums[i].clear();<br /> sum(tmp, sums[i]);<br /> }<br /> //把结果保存到了sums数组中<br /> int ni[12] = { 0 };<br /> bool success = false;<br /> int result = 0;<br /> while (!success)<br /> {<br /> for (int i = 0; i <= m; ++i)<br /> {<br /> result = max(result, sums[i][ni[i]]);<br /> }<br /> for (int i = 0; i <= m; ++i)<br /> {<br /> while (sums[i][ni[i]] < result)<br /> ++ni[i];<br /> }<br /> success = true;<br /> for (int i = 0; i <= m; ++i)<br /> {<br /> if (sums[i][ni[i]] != result)<br /> success = false;<br /> }<br /> }<br /> //这里很巧妙,用了现行推进的<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>每次找到最小,同时向前推进.如果最小不相同则又从刚结束的问题推进</p> <p> cout << "Scenario " << I << ":" << endl;<br /> cout << result << endl << endl;<br /> }<br /> }</p> <p>

很好的一个问题,这个思想真的很重要.首先构造出所有n个连续数和,然后利用一个O(n)的算法找到我们所要求的最小值!