题目传送门
【题目大意】
求一个数膜上一串数后的结果。
真的是特别简单的题意……
【思路分析】
因为要求很多个数连续膜上一串数后的结果，所以显而易见的，暴力会挂掉，于是考虑更优秀的做法。可以显然地得到一个结论，如果$a<b$，要求$a%b$，那么答案还是$a$，所以显然我们可以省去$%b$的步骤，于是我们可以将这个结论用于优化暴力做法。
首先是保证要膜的连续一串数单调递减，因为膜完了前面一个数之后的答案一定小于等于前面的数。
然后要膜的时候先找到最大的比输入的数据小的膜数，膜完之后再找最大的比当前答案小的膜数，重复操作，可以通过二分快速实现。
【代码实现】
1 #include<cstdio> 2 #define rg register 3 #define go(i,a,b) for(rg int i=a;i<=b;i++) 4 #define il inline 5 #define g getchar() 6 #define pf printf 7 using namespace std; 8 const int INF=1e9+7; 9 const int N=1e5+2; 10 int T,n,m,a[N]; 11 il int fr(){ 12 int w=0,q=1; 13 char ch=g; 14 while(ch<'0'||ch>'9'){ 15 if(ch=='-') q=-1; 16 ch=g; 17 } 18 while(ch<='9'&&ch>='0') w=(w<<1)+(w<<3)+ch-'0',ch=g; 19 return w*q; 20 } 21 il int work(rg int x){ 22 rg int l,r,mid,now; 23 while(1){ 24 now=0,l=1,r=n+1; 25 while(l<=r){ 26 mid=(l+r)>>1; 27 if(a[mid]<=x) now=mid,r=mid-1; 28 else l=mid+1; 29 } 30 if(now>n) break; 31 x%=a[now];//now记录找到的膜数 32 } 33 return x; 34 } 35 int main(){ 36 T=fr();a[0]=INF; 37 //因为保证单调递减所以a[0]取正无穷 38 while(T--){ 39 n=fr(); 40 rg int num=0; 41 go(i,1,n){ 42 rg int x=fr(); 43 if(x<a[num]) a[++num]=x;//单调递减 44 } 45 n=num;m=fr(); 46 go(i,1,m){ 47 rg int x=fr(); 48 pf("%d\n",work(x)); 49 } 50 } 51 return 0; 52 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11424013.html
