題目連結(jié)：
題目大意：
輸入第一列給定一正整數(shù) t（t ≦ 5），代表有 t 筆測試資料。每筆第一列給定兩正整數(shù) n 、 k（n ≦ 2000000，k ≦ 1000000000），代表有 n 個人。接著第二列給定 n 個整數(shù)，代表這 n 個人所在的位置 a （0 ≦ a ≦ 1000000000，且保證為由小到大給定）；第三列同樣也給定 n 個整數(shù)，代表這 n 個人的孤單評測值 w （-1000 ≦ w ≦ 1000）。
對於每一筆測資請輸出該 n 個人的孤單值總和。
一個人的孤單值為他的「孤單評測值」與「與他距離超過 k 單位長的其他人之孤單評測值總和」之乘積。
範(fàn)例輸入：
1
5 3
1 2 3 4 5
2 3 4 5 6
範(fàn)例輸出：
12
解題思維：
我們可以利用一個佇列 Q（Queue）來找出距離每個位置超過 k 單位長的那些位置。
一開始 Q 為空。此時我們定義一個變數(shù) S，用來統(tǒng)計孤單評測值的總和。
接著我們按照給定的順序掃過每個人的位置以及孤單評測值。先判斷 Q 的前端（代表目前佇列中離目前這個人最遠(yuǎn)的人之位置）是否距離當(dāng)前這個人超過 k 單位長。如果是則將 Q 的前端的那個人之孤單評測值加進(jìn) S 裡面。因為先前的人如果距離前一個人超過 k 單位，則對於目前的人也是如此（因為位置為由小到大給定）。重複此步驟直到 Q 為空或是條件不再符合。
之後我們將目前這個人的位置放到 Q 的尾端，並計算出 S × 當(dāng)前這個人的孤單評測值之乘積值便可以求得這個人與先前的人所將貢獻(xiàn)的孤單值總和。而當(dāng)前這個人與其後的人之孤單值總和將會由後面的人計算出來。
因此掃完所有人之後我們便可以求得所有人的孤單值之總和。
不過因為輸入之資料量相當(dāng)?shù)佚嫶蟆Ｐ枰罴鸦敵鋈氲乃俣龋ㄙY料量大到甚至這題提及的也有機(jī)會不行，因此需要改為 scanf 或甚至是自己撰寫，如這題）。嫌這樣不夠的話，還可以嘗試開啟編譯器方面的最佳化選項（如這題）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
