jayw711kb@gmail.com
(Jay Huang)
學校
:
國立虎尾科技大學
編號 : 119439
來源 : [27.247.130.217]
最後登入時間 ：
2020-09-15 15:55:19
我遇到的問題點:先用cin,cout串流,TLE,,TLE,緊接著我用函式scanf(),printf(),還是一樣TLE(花了約1s)qq.
然後我看了前兩篇的解題報告,才知道要如何寫.
TLE解題思路:
輸入範圍,一個一個慢慢加(講直接一點,就是一筆一筆處理),
其次數:一筆要處理l-r次,所以一組測資要迴圈會執行(l1-r1+1)+(l2-r2+1)+...+(lm-rm+1)=sigma(li-ri+1) (l<=i<=r)次.
註:如果看不懂可以直接往範例看,不必浪費時間在上一行.
AC解題思路:
假設 A為飽足度表SUM為累加表
先輸入飽足度時,一邊算累加表SUM,其答案等於SUM[r]-SUM[l-1],
其次數:每組測資一開始為了建立累加表迴圈先執行n次,後來部要用迴圈即可得到答案
(重要)註:若你在建立累加表多用一層迴圈,會增加時間複雜度(如下範例:迴圈會多執行((1+n)*n/2)-n)次),所以最好用類似遞迴概念
註:在BETTER SOLUTION裡,一邊讀入資料一邊建立累加表,這樣可以少用一個for.
NO:
for(int i=0;i<n;i++)
{
SUM[i]=0;
scanf("%d",&A[i]);
for(int j=0;j<i;j++)SUM[i]+=A[i];
}
BETTER SOLUTION:
SUM[0]=0;
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
SUM[i+1]=SUM[i]+arr[i];
}
範例:
輸入:
12 10
2 3 4 5 6 7 8 9 10 11 12 13
2 5
4 8
7 9
4 5
2 6
3 7
8 10
5 11
10 11
9 12
次數:
TLE: (5-2+1)+(8-4+1)+(9-7+1)+...+(12-9+1)=40
AC:12(建立累加表)
lintzuliang
(unknown)
學校
:
臺北市立育成高級中學
編號 : 153515
來源 : [140.134.204.172]
最後登入時間 ：
2023-03-03 11:07:02
yee54321000@gmail.com
(Yang Albert)
學校
:
臺北市立成功高級中學
編號 : 194981
來源 : [101.10.92.157]
最後登入時間 ：
2024-06-07 17:52:34
我遇到的問題點:先用cin,cout串流,TLE,,TLE,緊接著我用函式scanf(),printf(),還是一樣TLE(花了約1s)qq.
然後我看了前兩篇的解題報告,才知道要如何寫.
TLE解題思路:
輸入範圍,一個一個慢慢加(講直接一點,就是一筆一筆處理),
其次數:一筆要處理l-r次,所以一組測資要迴圈會執行(l1-r1+1)+(l2-r2+1)+...+(lm-rm+1)=sigma(li-ri+1) (l<=i<=r)次.
註:如果看不懂可以直接往範例看,不必浪費時間在上一行.
AC解題思路:
假設 A為飽足度表SUM為累加表
先輸入飽足度時,一邊算累加表SUM,其答案等於SUM[r]-SUM[l-1],
其次數:每組測資一開始為了建立累加表迴圈先執行n次,後來部要用迴圈即可得到答案
(重要)註:若你在建立累加表多用一層迴圈,會增加時間複雜度(如下範例:迴圈會多執行((1+n)*n/2)-n)次),所以最好用類似遞迴概念
註:在BETTER SOLUTION裡,一邊讀入資料一邊建立累加表,這樣可以少用一個for.
NO:
for(int i=0;i
{
SUM[i]=0;
scanf("%d",&A[i]);
for(int j=0;j
}
BETTER SOLUTION:
SUM[0]=0; for(int i=0;i
範例:
輸入:
12 10
2 3 4 5 6 7 8 9 10 11 12 13
2 5
4 8
7 9
4 5
2 6
3 7
8 10
5 11
10 11
9 12
次數:
TLE: (5-2+1)+(8-4+1)+(9-7+1)+...+(12-9+1)=40
AC:12(建立累加表)
這個真的要推