前言

寫寫題

題目相關

link

題目大意

給你$n$個正整數$a_i$
$$f(x)=\sum _{i=1}^n(a_i\%x+a_i/x)$$
$x$為正整數，求最小的$f(x)$

數據范圍

$n\le 10^6,a_i\le 10^6$

題解

開個桶，然后前綴和即可
對于所有的數枚舉轉移區間
復雜度$\mathcal{O}(nlogn)$
代碼

#include<cstdio> #include<cctype> #include<algorithm> #include<vector> #include<cstring> #define rg register typedef long long ll; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } const int maxn=2000001; int n,a[maxn]; ll ans,ANS; int main() {read(n);for(rg int i=1;i<=n;i++){int x;read(x);a[x]++;ANS+=x;}ans=ANS;for(rg int i=1;i<=2000000;i++)a[i]+=a[i-1];for(rg int x=1;x<=1000000;x++){ll res=ANS;for(rg int i=x;i<=1000000;i+=x)res-=(ll)i/x*(a[i+x-1]-a[i-1])*(x-1);mind(ans,res);}print(ans);return 0; }

總結

關鍵是要發現沒有性質，于是只能暴力

總結

以上是生活随笔為你收集整理的[uoj24]缩紧优化的全部內容，希望文章能夠幫你解決所遇到的問題。

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