http://ac.jobdu.com/problem.php?pid=1554
copy from http://blog.csdn.net/u013491262/article/details/21406351
把sum[1~i] = sum[i], sum[i] 是以a[i]为最后一个元素的前缀和，
Map以前缀和为key， 具有相同的前缀和的idx的vector 为value。
查找是以sum[i-1]+k 的key查找， 复杂度为O(logn) 找到后，找第一个比i大的那个idx。
#include <cstdio> #include <vector> #include <map> #include <cstring> using namespace std; #define inone(i) scanf("%d",&i) #define rep(i,j,k) for(int i=j;i<=k;i++) #define ms(x,y) memset(x,y,sizeof(x)) const int maxn = 2e6 + 10; map<int, vector<int> > idxs; int c[maxn], n, k, a, flag; int main() { while (inone(n) != EOF) { ms(c, 0); idxs.clear(); rep(i, 1, n) { inone(a); c[i] = c[i - 1] + a; idxs[c[i]].push_back(i); } inone(k); flag = 0; rep(i, 0, n-1) { if (idxs.find(c[i] + k) == idxs.end()) continue; vector<int> vI = idxs[c[i] + k]; rep(j, 0, vI.size()-1) { if (vI[j] >= i + 1) { printf("%d %d\n", i + 1, vI[j]); flag = 1; break; } } if (flag) break; } if(!flag) printf("No\n"); } return 0; }
