二分強(qiáng)化——浮點(diǎn)數(shù)序列查詢

TimeLimit:4000MS??MemoryLimit:128MB 64-bit integer IO format:%I64d Problem Description

已知在二維空間中有n個(gè)點(diǎn)，p0,p1……pn-1

已按照x為第一優(yōu)先級(jí)，y為第二優(yōu)先級(jí)從大到小排好序；

即若 pi<pj

則pi.x<pj.x,或者pi.x==pj.x&&pi.y<pj.y

Input

只有一組數(shù)據(jù)
第一行是兩個(gè)整數(shù)n,m分別代表點(diǎn)的個(gè)數(shù)和查詢次數(shù)
接下來(lái)n行，每行有二個(gè)帶三位小數(shù)的浮點(diǎn)數(shù)x,y代表一個(gè)點(diǎn)的坐標(biāo)
再接下來(lái)m行，每行的有4個(gè)數(shù)字x1,y1,x2,y2代表p1,p2且p1>=p2

其中n,m<=100000;

任意0<=x,y<10^6;

Output

輸出n個(gè)點(diǎn)所有小于等于p1且大于等于p2的點(diǎn)的下標(biāo)之和

SampleInput 6 4 125.689 125.689 125.689 125.688 125.688 125.689 125.688 125.689 125.688 125.688 125.688 125.688 125.688 125.688 125.688 125.688 125.688 125.689 125.688 125.688 125.689 125.689 125.688 125.689 125.688 125.689 125.688 125.689 SampleOutput 9 14 6 5
　　首先第一思路一個(gè)一個(gè)比較，當(dāng)由于數(shù)據(jù)龐大且有從大到小排列的小提示，顯然是二分。之后就是構(gòu)建數(shù)組寫(xiě)二分函數(shù)。
　　構(gòu)建數(shù)組有個(gè)小技巧，把第一優(yōu)先級(jí)乘一個(gè)較大的數(shù)，次優(yōu)先級(jí)乘較小數(shù)獲得的一個(gè)數(shù)字。恰好符合題目的比較條件。之后利用二分上下界函數(shù)找數(shù)字之間個(gè)數(shù)就完成了。接下來(lái)是這題的小細(xì)節(jié)，浮點(diǎn)數(shù)精度缺失的問(wèn)題。

?

浮點(diǎn)數(shù)運(yùn)算都會(huì)有精度缺失，轉(zhuǎn)換整型也會(huì)有缺失。只是缺失比較小。當(dāng)數(shù)據(jù)大的時(shí)候誤差就出現(xiàn)了。

這題將兩個(gè)浮點(diǎn)數(shù)整合為整數(shù)就可能遇到這個(gè)問(wèn)題。

注意運(yùn)算先后可能發(fā)生的精度缺失，然后用0.1補(bǔ)精度這一小技巧成功AC。（乘1000后，最小分度為1）。

另外1e9是浮點(diǎn)數(shù)，也會(huì)有進(jìn)度缺失，最好改1000000000.這題被我水過(guò)去

最后附上這題我的二分函數(shù)，及調(diào)用。最后記得連續(xù)下標(biāo)和是一個(gè)等差數(shù)列

long long f(ll *arr,int len,double x) {long long r=-1,l=len,mid;while(r+1<l){mid=(r+l)/2;if(arr[mid]>x){r=mid;}else{l=mid;}}return l; } View Code i=f(arr,n,p1);j=f(arr,n,p2-1);sum=(i+j-1)*(j-i)/2; View Code

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Q1143316492/p/6293044.html

總結(jié)

以上是生活随笔為你收集整理的FJUT寒假第一周作业浮点数查寻题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。