題目分析：

首先要想兩個暴力，一個的時間復雜度是$O(n^2)$,另一個是$O([\frac{n}{k}])$的。

$n^2$的暴力可以枚舉兩段，一段有$i$個取兩個的小朋友，一段有$j$個取兩個的小朋友。

你就可以算出每輪選取他們的代價，假設為$alpha$和$beta$。你要做的只是解$ (x+1)*alpha+x*beta=k $，不難解決。

?

然后是$O([\frac{n}{k}])$的暴力，枚舉選舉的輪數，也就是上面的$x$。首先假設每個小朋友選一個糖果，然后問題變為小朋友選或不選糖果。

引入新參數$gamma$來表示現在你需要小朋友選的糖果數。

這樣不難發現一組解是$(gamma,-gamma)$。然后兩個解的選擇范圍為$[0 or 1,len1]$和$[0,len2]$。調一調就行了。

?

代碼：

1 #include<bits/stdc++.h> 2 using namespace std; 3 4 long long n,l,r,k; 5 6 long long func(long long x,long long y,long long ki,int dr,long long ll,long long rr){ 7 if(y == 0){ 8 if(ki == 0 && dr == -1) return -1; 9 if(ki <= ll) return ki+rr; 10 else return -1; 11 } 12 long long a = ki,b = -ki; 13 long long hh = a/y;a %= y; b += hh*x; 14 if(a > ll) return -1; 15 if(dr == 1){ 16 if(b < 0) return -1; 17 if(b <= rr)return b+a; 18 else { 19 hh = (b-rr)/x+((b-rr)%x!=0); 20 b -= hh*x; 21 a += hh*y; 22 if(a <= ll) return b+a; 23 else return -1; 24 } 25 }else{ 26 if(a == 0) a += y,b -= x; 27 if(b < 0) return -1; 28 if(b <= rr) return b+a; 29 else { 30 hh = (b-rr)/x+((b-rr)%x!=0); 31 b -= hh*x; 32 a += hh*y; 33 if(a <= ll) return b+a; 34 else return -1; 35 } 36 } 37 } 38 39 int main(){ 40 scanf("%I64d%I64d%I64d%I64d",&n,&l,&r,&k); 41 long long um = (r-l+n)%n; 42 l = 1; r = 1+um; 43 if(k/n <= 5e6){ 44 long long len1 = r-l+1,len2 = n-len1; 45 long long ans = -1; 46 for(int i=0;i<=k/n;i++){ 47 long long zeta = k-i*n-len1; 48 if(zeta>=0)ans = max(ans,func(i+1,i,zeta,1,len1,len2)); 49 zeta = k+1-i*n-len1; 50 if(zeta>=0)ans = max(ans,func(i+1,i,zeta,-1,len1,len2)); 51 } 52 printf("%I64d",ans); 53 }else{ 54 int len1 = r-l+1,len2 = n-len1; 55 int ans = -1; 56 for(int i=0;i<=len1;i++){ 57 for(int j=0;j<=len2;j++){ 58 int alpha = len1+i,beta = len2+j; 59 long long zeta = k-alpha; 60 if(zeta % (alpha+beta) == 0) ans = max(ans,i+j); 61 } 62 } 63 k++; 64 for(int i=1;i<=len1;i++){ 65 for(int j=0;j<=len2;j++){ 66 int alpha = len1+i,beta = len2+j; 67 long long zeta = k-alpha; 68 if(zeta % (alpha+beta) == 0) ans = max(ans,i+j); 69 } 70 } 71 printf("%d",ans); 72 } 73 return 0; 74 }

?

轉載于:https://www.cnblogs.com/Menhera/p/9873516.html

總結

以上是生活随笔為你收集整理的Codeforces1063D Candies for Children 【分类讨论】【暴力】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。