我的任務很簡單，但最明顯的解決方案是太慢了。
我有大量的積極因素和一些與這個大規模相關的問題。我必須找到元素總和小于給定 S 的最長段 (l,r)（給定 l）。我的代碼應該是 C 語言，我試圖用微不足道的for或while（剛剛開始回圈 l 元素并在總和小于 S 時走得更遠，但它太慢了）。我的老師建議我計算從0to的所有總和i并使用這些總和來找到所需的段 (l,r)，但我真的不知道如何做到這一點。測驗示例：
10 7
1
4
0
5
6
0
0
1
5
3
0 100
0 5
4 11
4 12
4 13
10 100
第一個數字N( 10) 是海量元素的數量
第二個數字K( 7) 是測驗的數量
接下來 10 個數字 ( 1,4,0,5,6,0,0,1,5,3) 是陣列
的元素 最后 7 對元素是測驗（第一個數字是l，第二個是sum）
并且答案是
10
3
8
9
9
10
8
我的代碼
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
uint32_t Query (uint32_t l, uint64_t sum,const uint32_t *arr,uint32_t n);
int main() {;
FILE *f = fopen("input.txt","r");
FILE *s = fopen("output.txt","w");
uint32_t n,t,l;
uint64_t sum;
fscanf(f,"%d",&n);
fscanf(f,"%d",&t);
uint32_t *arr = malloc(sizeof (uint32_t) * n);
for( int i = 0; i < n; i ){
fscanf(f,"%d",&arr[i]);
}
for( int i = 0; i < t; i ){
fscanf(f,"%d %lld",&l,&sum);
Query(l,sum,arr,n);
}
return 0;
}
uint32_t Query (uint32_t l, uint64_t sum,const uint32_t *arr,uint32_t n){
uint64_t summy = 0;
uint32_t i;
for( i = l ; i < n; i ){
summy = arr[i];
if (summy > sum){
return i;
}
}
return i;
}
uj5u.com熱心網友回復：
我認為您的老師的意思是，而不是存盤arr[i] = input_i：
for( int i = 0; i < n; i ){
fscanf(f,"%d",&arr[i]);
}
您可以存盤運行總和，arr[i] = \sum_{n=0}^{i} input_n. 這是積分的離散版本。
int energy = 0; /* Or whatever. */
for( int i = 0; i < n; i ) {
int value;
if(fscanf(f,"%d",&value) != 1) exit(EXIT_FAILURE);
energy = value;
arr[i] = energy;
}
unsigned int如果您有很多值，您可能必須切換到，因為它是一個環，而int如果它超過，則具有未定義的特征INT_MAX，（但可能有效。）因為問題是線性的，這允許您只查看端點, arr[r] - arr[l]. 因此，您可以減少每一步的增量O(n)，并使用二進制搜索，O(log n)。具體來說，您需要采用上限。與bsearchC 類似，但在std::upper_bound中。
uj5u.com熱心網友回復：
為了速度；如果您知道段 (l, r) 的總和，那么您可以通過減去 array[l] 處的條目并添加 array[r 處的條目來確定段的總和 (l 1, r 1) 1]。
因此（未經測驗）：
void FindHighestSum (const uint32_t *array, uint32_t arraySize, uint32_t segmentSize) {
uint32_t bestSumPos;
uint64_t bestSum;
uint32_t r;
uint32_t l;
uint64_t sum = 0;
if(arraySize < segmentSize) {
printf("Error: Array too small for segment size\n");
return;
}
// Find sum of first segment
for(r = 0; r < segmentSize; r ) {
sum = array[r];
}
// Sum of first segment is the largest sum so far
bestSumPos = 0;
bestSum = sum;
// Find largest sum of all segments
for(l = 1; l < arraySize - segmentSize; l ) {
sum = sum - array[l] array[r];
r ;
if(sum > bestSum) {
// Found a new largest sum
bestSumPos = l;
bestSum = sum;
}
}
printf("Highest sum from %" PRIu32 " to %" PRIu32 " (sum is %" PRIu64 ")\n", bestSumPos, bestSumPos segmentSize - 1, bestSum);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/434841.html
下一篇：如何將pythonapi或本地資料呼叫到jslibgoogle.visualization.DataTable()中？