wordpress 徹底加速落實(shí)好疫情防控優(yōu)化措施
題目:
?
樣例解釋:
?
樣例1解釋
拿?k=20?塊糖放入籃子里。
籃子里現(xiàn)在糖果數(shù)?20≥n=7,因此所有小朋友獲得一塊糖;
籃子里現(xiàn)在糖果數(shù)變成?13≥n=7,因此所有小朋友獲得一塊糖;
籃子里現(xiàn)在糖果數(shù)變成?6<n=7,因此這?6?塊糖是作為你搬糖果的獎(jiǎng)勵(lì)。
容易發(fā)現(xiàn),你獲得的作為你搬糖果的獎(jiǎng)勵(lì)的糖果數(shù)量不可能超過(guò)?6?塊(不然,籃子里的糖果數(shù)量最后仍然不少于?n,需要繼續(xù)每個(gè)小朋友拿一塊),因此答案是?6。
樣例2解釋
容易發(fā)現(xiàn),當(dāng)你拿的糖數(shù)量?k?滿足?14=L≤k≤R=18?時(shí),所有小朋友獲得一塊糖后,剩下的?k?10?塊糖總是作為你搬糖果的獎(jiǎng)勵(lì)的糖果數(shù)量,因此拿?k=18?塊是最優(yōu)解,答案是?8。
思路:
70分思路:
暴力枚舉?[l,r][l,r]?中的每一個(gè)整數(shù)并統(tǒng)計(jì)答案。
?
100分思路:
取余運(yùn)算的兩個(gè)簡(jiǎn)單性質(zhì):
(大概是小學(xué)知識(shí)吧)
nn?對(duì)任何正整數(shù)取余的結(jié)果都在?[0,n?1][0,n?1]范圍內(nèi)
若?x?mod?n=yxmodn=y,則?(x+n)?mod?n=y(x+n)modn=y
因此我們能知道:
若?r?l+1≥nr?l+1≥n,則?[0,n?1][0,n?1]?中的每個(gè)正整數(shù)都能在?[l,r][l,r]中的正整數(shù)對(duì)?nn?取余的結(jié)果中找到,此時(shí)答案為?n?1n?1
若?r?l+1<nr?l+1<n,則再分類討論:
若?l?mod?n≤r?mod?nlmodn≤rmodn,如下圖
此時(shí)能取到的數(shù)的范圍為上圖的紅色部分,這時(shí)答案為?r?mod?nrmodn
注意:?這里的分類是?l?mod?n≤r?mod?n l mod n≤r mod n,而非?l? mod ?n<r? mod?n l mod n<r mod n
若?l? mod? n>r? mod?n lmod n>r mod n,如下圖
此時(shí)能取到的數(shù)的范圍為上圖的紅色部分,這時(shí)答案為?n?1
代碼:
#include<iostream>
#include<cstdio>
using namespace std;int n,l,r;int main(){cin>>n>>l>>r;if(l/n==r/n) cout<<r%n;else cout<<n-1;return 0;
}
總結(jié):
此題解題關(guān)鍵為分類討論,必須貫徹不重不漏的原則,否則有可能出錯(cuò)?
?
?