1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define nmax 100010 5 6 using namespace std; 7 int a[nmax]; 8 int n, s; 9 10 bool f(int& p, int& sum){ 11 while (sum<s && p<n) sum += a[++p]; 12 return (p==n && sum<s); 13 } 14 15 int main(){ 16 int cas; 17 cin >> cas; 18 while(cas--){ 19 scanf("%d%d", &n, &s); 20 for (int i=1; i<=n; i++) scanf("%d", &a[i]); 21 int p=0, sum=0; 22 if( f(p, sum) ) { printf("0\n"); continue; } 23 int r=p, ans=p; 24 for (int l=2; l<=n; l++) { 25 sum -= a[l-1]; 26 if( f(r, sum) ) break; 27 ans = min(ans, r-l+1); 28 } 29 printf("%d\n", ans); 30 } 31 return 0; 32 }
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define nmax 100010 5 #define f(l,r) (s[r].first-s[l].first) 6 7 using namespace std; 8 typedef long long ll; 9 ll n, k, t; 10 ll a[nmax]; 11 pair<ll,int> s[nmax]; 12 const ll inf = 1e15;//这里只开到1e9会wa 13 int r, ansl, ansr, l; 14 ll ans, tmp=inf; 15 16 inline void newa(int l, int r) { 17 if( abs( t-f(l,r) ) < tmp ) { 18 tmp = abs( t-f(l,r) ); 19 ansl = s[l].second; 20 ansr = s[r].second; 21 ans = f(l,r); 22 } 23 } 24 25 void solve(){ 26 tmp = inf; r=1; 27 for (l=0; l<n; l++) { 28 if(r<=l) r=l+1; 29 while(f(l,r)<t && r<=n){ 30 newa(l,r); 31 if(f(l,r)==t) break; 32 r++; 33 } 34 if(r>n) break; 35 newa(l,r); 36 } 37 if(ansl>ansr) swap(ansl,ansr); 38 } 39 40 int main(){ 41 while(scanf("%I64d%I64d", &n, &k)!=EOF && (n||k) ){ 42 s[0].first = s[0].second = 0; 43 for (int i=1; i<=n; i++) { 44 scanf("%lld", &a[i]); 45 s[i].first = s[i-1].first + a[i]; 46 s[i].second = i; 47 } 48 sort(s, s+n+1); 49 while(k--){ 50 scanf("%I64d", &t); 51 solve(); 52 printf("%I64d %d %d\n", ans, ansl+1, ansr); 53 } 54 } 55 return 0; 56 }
原文:https://www.cnblogs.com/jiecaoer/p/11894845.html