贪默算法条记

贪默算法条记

大概内容

贪心就是对于一个标题有很多个步调，我们在每一个步调中都选取最优的那一个，末了得出答案。就是在一些函数中可行，但是有些好比二次函数，由于它的迁移转变点不肯定最优，就是不可行的。那么怎样判定贪心呢？有这么几种

• 看时间复杂度，一样寻常的就是                                    O                         (                         n                         )                              O(n)                  O(n) 大概是排序                                    O                         (                         n                                                   l                         o                         g                         n                         )                              O(n \ log n)                  O(n logn)​
  
• 大概推测，看着像就可以试试。
  
• 自己用数学证实方法，好比归纳法，互换法，就是假如互换之后答案变得小大概大就可以了。
  

那贪心在比赛中怎么办呢？可以先实验一下巨细样例，再实验对拍，有个保底，假如可以也可以证实一下。
然后另有一种贪心，叫做反悔贪心，就是可以打消，也没别的。
末了由于贪心每次取局部最优，以是代码不长，而且时间复杂度不大。
例题解说

缭乱的yyy / 线段覆盖

标题大意:有                               n                          n               n 个线段，问最多有多少个不重叠的线段。
思绪：贪心，然后按照                                        r                         i                                  r_{i}               ri​ 排序，每次选取尽大概早的场次而且要合法，也就是不能前面重叠。
证实：假如不相交，那么图片如下。

很显着，一场弄完，另一场。假如包罗，图片如下：

那样我们就可以选择第一场，由于它竣事得早，可以取别的的场次。以是证实取更早的是永久比更晚的要更优。
时间复杂度：                              O                      (                      n                      log                      ⁡                      n                      )                          O(n \log n)               O(nlogn)

1. #include<bits/stdc++.h>
2. struct noip//有同学不会结构体的多开几个数组
3. {
4.         int begin;//开始时间
5.         int finish;//结束时间
6. }a[2000005];
7. bool cmp(noip x,noip y)
8. {
9.         return x.finish<y.finish;//按结束时间排
10. }
11. using namespace std;
12. int main()
13. {
14.         int n,ans=1;//初始化
15.         cin>>n;
16.         for(int i=1;i<=n;i++)
17.         {
18.                 cin>>a[i].begin>>a[i].finish;
19.         }
20.         sort(a+1,a+n+1,cmp);//快速排序(不用我多说了吧)
21.         int mini=a[1].finish;//定义mini统计最后结束时间
22.         int j=1;
23.         while(j<=n)//我用了while,感兴趣的同学可以用for(提示：for不用定义j)
24.         {
25.                 j++;
26.                 if(a[j].begin>=mini)//新的比赛开始时间要晚于mini
27.                 {
28.                         ans++;//统计比赛数
29.                         mini=a[j].finish;//更新mini
30.                 }
31.         }
32.         cout<<ans<<endl;//输出
33.         return 0;//功德圆满
34. }

复制代码

Teleporters (Easy Version)

思绪：直接                                        a                         i                              +                      i                          a_{i}+i               ai​+i 排序，就好了。
证实：就是每次都是走已往，传返来，以是直接排序就可以了。
时间复杂度：                              O                      (                      n                      log                      ⁡                      n                      )                          O(n \log n)               O(nlogn)

1. #include<bits/stdc++.h>
2. using namespace std;
3. struct node
4. {
5.         int x,id;
6. }c[200005];
7. int n,m,tmp;
8. bool cmp(node a,node b)
9. {
10.         return a.x+a.id<=b.x+b.id;//跟思路一样排序
11. }
12. int main()
13. {
14.         int t;
15.         cin>>t;
16.         while(t--)
17.         {
18.                 memset(c,0,sizeof(c));
19.                 cin>>n>>m;
20.                 for(int i=1;i<=n;i++)
21.                 {
22.                         cin>>tmp;
23.                         c[i].x=tmp;
24.                         c[i].id=i;
25.                 }
26.                 sort(c+1,c+n+1,cmp);
27.                 int i=0;
28.                 while(m>=0&&i<=n)
29.                 {
30.                         i++;
31.                         m=m-c[i].x-c[i].id;
32.                 }
33.                 cout<<i-1<<endl;       
34.         }
35.         return 0;
36. }

复制代码

Teleporters (Hard Version)

思绪：这一题就是先前缀和记录一下能用的传送门的代价之和，然后在使用二分答案，但是由于出发点是                               0                          0               0 的缘故，以是还要别的罗列                               0                          0               0 点。

1. #include<bits/stdc++.h>
2. #define maxn 2900001
3. #define int long long
4. using namespace std;
5. int T,n,m,ans,a[maxn],s[maxn];
6. int check(int c,int x,int id)
7. {//二分最长的合法前缀区间
8.         int l=1,r=n,sum=-1;
9.         while(l<=r)
10.         {
11.                 int mid=l+r>>1;
12.                 if(s[mid]-(mid>=id?x:0)<=c)
13.                  sum=mid+(mid>=id?-1:0),l=mid+1;//特判x的影响
14.                 else
15.                         r=mid-1;
16.         }
17.         return sum==-1?0:sum;//可能无解
18. }
19. signed main()
20. {
21.         scanf("%lld",&T);
22.         while(T--)
23.         {
24.                 ans=0;
25.                 map<int,int>mp;//记录位置
26.                 scanf("%lld%lld",&n,&m);
27.                 for(int i=1;i<=n;i++)
28.                 {
29.                         scanf("%lld",&a[i]);
30.                         s[i]=min(a[i]+(n-i+1),a[i]+i);//取最小花费
31.                 }
32.                 sort(s+1,s+n+1);
33.                 for(int i=1;i<=n;i++)
34.                         mp[s[i]]=i,s[i]+=s[i-1];//前缀和
35.                 for(int i=1;i<=n;i++)
36.                 {
37.                         if(m-a[i]-i<0)
38.                                 continue;//可能不合法
39.                         ans=max(ans,check(m-a[i]-i,min(a[i]+(n-i+1),a[i]+i),mp[min(a[i]+(n-i+1),a[i]+i)])+1);//注意要加上当前点i
40.                 }
41.                 printf("%lld\n",ans);
42.         }
43.         return 0;
44. }

复制代码

国王游戏

思绪:就是按照                                             a                            i                                            b                            i                                       a_ib_i                  ai​bi​​​的巨细从小到大排序
证实：我们不妨设两个人分别写了                                        a                         1                              ,                               b                         1                              ,                               a                         2                              ,                               b                         2                                  a_1,b_1,a_2,b_2               a1​,b1​,a2​,b2​ 且满意                                        a                         1                                       b                         1                              >                               a                         2                                       b                         2                                  a_1b_1>a_2b_2               a1​b1​>a2​b2​ 则有                                                  a                            2                                            b                            1                                       =                                         a                            1                                            b                            2                                           \tfrac{a_2}{b_1}=\tfrac{a_1}{b_2}               b1​a2​​=b2​a1​​​
以是有一下两种环境

• 1在2的前面
  
• 1在2的反面
  

设在设在                               1                      ,                      2                          1,2               1,2 之前全部人左手乘积为                               k                          k               k，那么对于第一种环境，我们的答案就是
                                                                                  a                                     n                                                   s                                        1                                                                                                 =                                                                                     max                                     ⁡                                     (                                                   k                                                       b                                           1                                                                ,                                                                  k                                                           a                                              1                                                                                    b                                           2                                                                )                                                                                                                          =                                                                                     k                                     ⋅                                     max                                     ⁡                                     (                                                   1                                                       b                                           1                                                                ,                                                                  a                                           1                                                                     b                                           2                                                                )                                                                        \begin{matrix}ans_1&=&\max(\frac{k}{b_1},\frac{ka_1}{b_2})\ &=& k\cdot \max(\frac{1}{b_1},\frac{a_1}{b_2})\end{matrix}                  ans1​​=​max(b1​k​,b2​ka1​​) ​=​k⋅max(b1​1​,b2​a1​​)​
                               ∵                                         a                            2                                            b                            1                                       <                                         a                            1                                            b                            2                                       ,                               a                         2                              >                      1                          \because \frac{a_2}{b_1} < \frac{a_1}{b_2},a_2>1               ∵b1​a2​​<b2​a1​​,a2​>1
                               ∴                               1                                   b                            1                                       ≤                                         a                            2                                            b                            1                                       <                                         a                            1                                            b                            2                                           \therefore \frac{1}{b_1} \leq \frac{a_2}{b_1} < \frac{a_1}{b_2}               ∴b1​1​≤b1​a2​​<b2​a1​​
                               ∴                      a                      n                               s                         1                              =                                         k                            ×                                       a                               1                                                      b                            2                                           \therefore ans_1=\frac{k \times a_1}{b_2}               ∴ans1​=b2​k×a1​​
对于第二种，答案就是
                               a                      n                               s                         2                              =                      m                      a                      x                      (                               k                                   b                            2                                       ,                                         k                            ×                                       a                               2                                                      b                            1                                       )                          ans_2=max(\frac{k}{b_2},\frac{k \times a_2}{b_1})               ans2​=max(b2​k​,b1​k×a2​​)
                               {                                                                             ∵                                                   a                                        1                                                  >                                     1                                                                                                                 ∴                                                                  k                                           ×                                                           a                                              1                                                                                    b                                           2                                                                ≥                                                   k                                                       b                                           2                                                                                                                                            ∵                                                                  a                                           2                                                                     b                                           1                                                                <                                                                  a                                           1                                                                     b                                           2                                                                                                                                            ∴                                                                  k                                           ×                                                           a                                              1                                                                                    b                                           2                                                                >                                                                  k                                           ×                                                           a                                              2                                                                                    b                                           1                                                                                                       \left\{\begin{matrix} \because a_1>1 \\ \therefore \frac{k \times a_1}{b_2} \ge \frac{k}{b_2}\\ \because \frac{a_2}{b_1}<\frac{a_1}{b_2} \\ \therefore \frac{k \times a_1}{b_2}>\frac{k \times a_2}{b_1}\end{matrix}\right.               ⎩             ⎨             ⎧​∵a1​>1∴b2​k×a1​​≥b2​k​∵b1​a2​​<b2​a1​​∴b2​k×a1​​>b1​k×a2​​​
                               ∴                      a                      n                               s                         1                              ≥                      a                      n                               s                         2                                  \therefore ans_1 \ge ans_2               ∴ans1​≥ans2​
以是按照 按照                                             a                            i                                            b                            i                                       a_ib_i                  ai​bi​的巨细从小到大排序的方法没有标题。
细节：留意高精度

1. #include<cstdio>
2. #include<cstring>
3. #include<algorithm>
4. using namespace std;
5. int N;
6. int a[1005],b[1005],ka,kb;
7. int ans[20000],t[20000],lena,lent,tt[20000],t2[20000],len;
8. void _qst_ab(int l,int r)
9. {
10.         int i=l,j=r,ma=a[(i+j)>>1],mb=b[(i+j)>>1];
11.         while(i<=j)
12.         {
13.                 while(a[i]*b[i]<ma*mb) i++;
14.                 while(a[j]*b[j]>ma*mb) j--;
15.                 if(i<=j)
16.                 {
17.                         swap(a[i],a[j]);
18.                         swap(b[i],b[j]);
19.                         i++;j--;
20.                 }
21.         }
22.         if(l<j) _qst_ab(l,j);
23.         if(i<r) _qst_ab(i,r);
24. }
25. void _init()
26. {
27.         scanf("%d%d%d",&N,&a[0],&b[0]);
28.         for(int i=1;i<=N;i++)
29.             scanf("%d%d",&a[i],&b[i]);
30. }
31. void _get_t(int Left,int Right)
32. {
33.         for(int i=1;i<=lent;i++)
34.         {
35.                 tt[i]+=t[i]*Left;
36.                 tt[i+1]+=tt[i]/10;
37.                 tt[i]%=10;
38.         }
39.         lent++;
40.         while(tt[lent]>=10)
41.         {
42.                 tt[lent+1]=tt[lent]/10;
43.                 tt[lent]%=10;
44.                 lent++;
45.         }
46.         while(lent>1&&tt[lent]==0) lent--;
47.         len=lent;
48.         memcpy(t,tt,sizeof(tt));
49.         memset(tt,0,sizeof(tt));
50.         for(int i=1,j=len;i<=len;i++,j--)
51.             t2[i]=t[j];
52.         int x=0,y=0;
53.         for(int i=1;i<=len;i++)
54.         {
55.                 y=x*10+t2[i];
56.                 tt[i]=y/Right;
57.                 x=y%Right;
58.         }
59.         x=1;
60.         while(x<len&&tt[x]==0) x++;
61.         memset(t2,0,sizeof(t2));
62.         for(int i=1,j=x;j<=len;i++,j++)
63.             t2[i]=tt[j];
64.         memcpy(tt,t2,sizeof(t2));
65.         len=len+1-x;
66. }
67. bool _cmp()
68. {
69.         if(len>lena) return true;
70.         if(len<lena) return false;
71.         for(int i=1;i<=len;i++)
72.         {
73.             if(ans[i]<tt[i]) return true;
74.             if(ans[i]>tt[i]) return false;
75.         }
76.         return false;
77. }
78. void _solve()
79. {
80.         _qst_ab(1,N);
81.         t[1]=1;lent=1;
82.         for(int i=1;i<=N;i++)
83.         {
84.                 memset(tt,0,sizeof(tt));
85.                 len=0;
86.                 _get_t(a[i-1],b[i]);
87.                 if(_cmp())
88.                 {
89.                     memcpy(ans,tt,sizeof(tt));
90.                     lena=len;
91.                 }
92.         }
93.         for(int i=1;i<=lena;i++)
94.             printf("%d",ans[i]);
95.         printf("\n");
96. }
97. int main()
98. {
99.         _init();
100.         _solve();
101.         return 0;
102. }

复制代码

[USACO07MAR] Face The Right Way G

思绪：就是使用贪心，遇到                               B                          B               B 的话就全部翻转。然后罗列长度。但是时间复杂度假如没有任何别的优化就是                               O                      (                               n                         3                              )                          O(n^3)               O(n3) 如许呢是过不了的，

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int maxn = 10009;
4. int n;
5. bool A[maxn],B[maxn];
6. int main()
7. {
8.         scanf("%d",&n);
9.         char ch;
10.         for(int i=1;i<=n;++i)
11.         {
12.                 cin>>ch;
13.                 A[i]=ch=='B'?0:1;
14.         }
15.         int mincnt=0x7fffffff,anslen;
16.         for(int len=1;len<=n;++len)
17.         {
18.                 memset(B,0,sizeof B);
19.                 bool b=0,flag=1;int cnt=0;
20.                 for(int i=1;i<=n;i++)
21.                 {
22.                         b^=B[i];
23.                         if(!(A[i]^b))
24.                         {
25.                                 if(i+len-1>n)
26.                                 {
27.                                         flag=0;
28.                                         break;
29.                                 }
30.                                 b^=1;
31.                                 B[i+len]^=1;
32.                                 ++cnt;
33.                         }
34.                 }
35.                 if(flag)
36.                 {
37.                         if(cnt<mincnt)
38.                         {
39.                                 mincnt=cnt;0
40.                                 anslen=len;
41.                         }
42.                 }
43.         }
44.         printf("%d %d\n",anslen, mincnt);
45. }

复制代码

异或与乘积题解

有                               n                          n               n 个数你可以将两个数字异或，终极将全部数字相乘，问总乘积最大是多少
由于答案大概很大，输出对                               1000000007                          1 000 000 007               1000000007 取模后的结果。
思绪概述
起首，我们必要相识一个标题：异或是什么东西?异或简单来说0就是而进制中的加法，也就是差别就是                               1                          1               1 ，假如雷同就是                               0                          0               0 。好的，那我们就可以相识一个事变，异或肯定小于便是加法，加法小于乘法，但是，有两种环境会出现反例，什么呢？就是有                               0                          0               0 的环境，但是不难发现，                                        a                         i                              ≥                      1                          a_{i} \ge 1               ai​≥1 以是不消管。另有一种就是                                        a                         i                              =                      1                          a_{i}=1               ai​=1 那么假如他异或偶数，那么就                               +                      1                          +1               +1 ，否则就                               −                      1                          -1               −1 。以是我们就先分离出                               1                          1               1 的位置，然后使用和肯定，差小积大的特点，把小的偶数先拿已往异或就可以了。

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int Mod=1e9+7;
4. int a[100010];
5. int b[100010];
6. int main()
7. {
8.         int n;
9.         cin>>n;
10.         long long ans=1;//一定要注意开long long 不然死得很惨。
11.         int cnt=0;
12.         int len=1;
13.         int len1=1;
14.         for(int i=1;i<=n;i++)//分离奇数和偶数，记录1的个数
15.         {
16.                 int x;
17.                 cin>>x;
18.                 if(x==1)
19.                 {
20.                         cnt++;
21.                 }
22.                 else
23.                 {
24.                         if(x&1)
25.                         {
26.                                 a[len++]=x;
27.                         }
28.                         else
29.                         {
30.                                 b[len1++]=x;
31.                         }
32.                 }
33.         }
34.         sort(b+1,b+len1);
35.         for(int i=1;i<len1;i++)//开始异或
36.         {
37.                 if(cnt-1>=0)
38.                 {
39.                         cnt--;
40.                         b[i]+=1;
41.                 }
42.         }
43.         for(int i=1;i<len1;i++)
44.         {
45.                 ans=1LL*(ans*b[i])%Mod;
46.         }
47.         for(int i=1;i<len;i++)
48.         {
49.                 ans=1LL*(ans*a[i])%Mod;
50.         }
51.         cout<<ans<<endl;
52.         return 0;
53. }

复制代码

更换字母2题解

标题大意
有长度为                               n                          n               n 的字符串，仅包罗小写字母。小信想把字符串酿成只包罗一种字母。他每次可以选择一种字符                               c                          c               c，然后把长度最多为                               m                          m               m 的子串中的字符都更换成                               c                          c               c 。小信想知道最少必要操纵频频能让字符串只包罗一种字母。
思绪分析
我一开始想怎么去贪心，结果怎么都不会，然后转头想去暴力，结果稍微加一点点贪心就过了。我们起首罗列26个小写字母，代表我们要把这一个字符串全部酿成这个小写字母，然后我们罗列下标                               j                          j               j 假如                                        s                         j                                  s_{j}               sj​ 和哪个                               i                          i               i 是一样的，那么就                               c                      o                      n                      t                      i                      n                      u                      e                          continue               continue ，假如不一样的话我们就将                               j                      +                      =                      m                      −                      1                          j+=m-1               j+=m−1 这里必须要留意，由于下次                                    j                         +                         +                              j++                  j++ 导致必须是                                    m                         −                         1                              m-1                  m−1 ，还要                               a                      n                      s                      +                      +                          ans++               ans++ 。

1. #include<bits/stdc++.h>
2. using namespace std;
3. string s;
4. string s1;
5. int main()
6. {
7.         int n,m;
8.         cin>>n>>m;
9.         cin>>s;
10.         int ans1=INT_MAX;
11.         for(int i=0;i<26;i++)
12.         {
13.                 int ans=0;
14.                 for(int j=0;j<n;j++)
15.                 {
16.                         if(s[j]==i+'a')
17.                         {
18.                                 continue;
19.                         }
20.                         else
21.                         {
22.                                 j+=m-1;
23.                                 ans++;
24.                         }
25.                 }
26.                 ans1 = min(ans1,ans);
27.         }
28.         cout<<ans1;
29.         return 0;
30. }

复制代码

平衡后缀

这一题思绪的话还是贪心，然后中央填一个表然后末了后缀取一下最大值和最小值

1. #include<bits/stdc++.h>
2. using namespace std;
3. int t,n,k,p,f,m[1001],vis[1001];
4. int main()
5. {
6.         cin>>t;
7.         while(t--)
8.         {
9.                 f=1;
10.                 p=0;
11.                 memset(vis,0,sizeof(vis));
12.                 memset(m,0,sizeof(m));
13.                 string s;
14.                 cin>>n>>k>>s;
15.                 for(int i=0;i<s.size();++i)
16.                 {
17.                         vis[s[i]-97]=1;
18.                         m[s[i]-97]++;
19.                         p=max(p,m[s[i]-97]);
20.                 }
21.                 for(int i=0;i<26;++i)
22.                 if(vis[i]&&p-m[i]>k)
23.                 {
24.                         cout<<-1;
25.                         f=0;
26.                         break;
27.                 }
28.                 if(f)
29.                 {
30.                         for(int i=0;i<s.size();++i)
31.                         {
32.                                 for(int j=0;j<26;++j)
33.                                 {
34.                                         if(m[j])
35.                                         {
36.                                                 int mx=0,mn=INT_MAX;
37.                                                 m[j]--;
38.                                                 for(int k=0;k<26;++k)
39.                                                 {
40.                                                         if(vis[k])
41.                                                         {
42.                                                                 mx=max(mx,m[k]);
43.                                                                 mn=min(mn,m[k]);
44.                                                         }
45.                                                         if(mx-mn>k)
46.                                                                 m[j]++;
47.                                                         else
48.                                                         {
49.                                                                 cout<<char(j+97);
50.                                                                 break;
51.                                                         }
52.                                                 }
53.                                         }                               
54.                                 }       
55.                         }
56.                 }
57.                 cout<<endl;
58.         }
59.         return 0;
60. }

复制代码

奶牛玩杂技

标题大意：每头牛都有自己的体重以及气力，编号为                               i                          i               i 的奶牛的体重为                                        W                         i                                  W_i               Wi​，气力为                                        S                         i                                  S_i               Si​。当某头牛身上站着另一些牛时它就会在肯定水平上被压扁，我们不妨把它被压扁的水平叫做它的压扁指数。对于恣意的牛，她的压扁指数便是摞在她上面的全部奶牛的总重（固然不包罗她自己）减去它的气力。奶牛们按照肯定的序次摞在一起后， 她们的总压扁指数就是被压得最扁的那头奶牛的压扁指数。
思绪概述：贪心，但是正常我们看到的贪心是只有一个变量的，但是这道标题有两个：分别是奶牛的重量和奶牛的力气。那让我们来思考一下：重量大的是不是应该放的更靠下？放的越靠下他的重量影响的奶牛就越少。以是                                        W                         i                                  W_i               Wi​ 越大越要越往下放。那么，奶牛力气越大的就越往下放也是雷同的原理，力气越大可以大概支持的重量越多，以是受到重量影响就越小，为了让最大值最小就应该让力气大的去遭受更多的重量由于一个力气小的和                               S                      1                          S1               S1 一个 力气大的                               S                      2                          S2               S2 去遭受同样的重量，                              W                      −                               S                         1                              <                      W                      −                               S                         2                                  W−S_1 < W−S_2               W−S1​<W−S2​ 以是力气越大的就应该越往下放这个时间就有两个必要贪心的了，但是，这是感性思考，必要理性，以是，开始证实。
假设只有两只奶牛，一只奶牛的重量为                               W                      1                          W1               W1 ，力气为                               S                      1                          S1               S1 。
另一只奶牛的重量为                                        S                         1                                  S_1               S1​ ，力气为                                        S                         2                                  S_2               S2​ 。
假如前者在下压扁指数即为                                        W                         2                              −                               S                         1                                  W_2−S_1               W2​−S1​ 。
假如后者在下压扁指数即为                                        W                         1                              −                               S                         2                                  W_1−S_2               W1​−S2​ 。
假设前者在下更优即为前者在下压扁指数更小
那么                                        W                         2                              −                               S                         1                              <                               W                         1                              −                               S                         2                                  W_2−S_1<W_1−S_2               W2​−S1​<W1​−S2​ 移项得                                        W                         2                              +                               S                         2                              <                               W                         1                              +                               S                         1                                  W_2+S_2<W_1+S_1               W2​+S2​<W1​+S1​ 这个时间是处于前者在下更优的环境下以是得出结论                                        W                         i                              +                               S                         i                                  W_i+S_i               Wi​+Si​ 越大就应该越往下放

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N=50005;
4. struct node
5. {
6.         int w,s;
7. }a[N];
8. int n,m;
9. bool cmp(node a,node b)
10. {
11.         return a.w+a.s<b.w+b.s;
12. }
13. int main()
14. {
15.         scanf("%d",&n);
16.         for(int i=1;i<=n;i++)
17.         {
18.                 scanf("%d%d",&a[i].w,&a[i].s);
19.         }
20.         sort(a+1,a+n+1,cmp);
21.         int ans=-1e9,tmp=0;
22.         for(int i=1;i<=n;i++)
23.         {
24.                 ans=max(ans,tmp-a[i].s);
25.                 tmp+=a[i].w;
26.         }
27.         printf("%d",ans);
28.         return 0;
29. }

复制代码

分金币

标题形貌：圆桌上坐着                               n                          n               n 个人，每人有肯定命量的金币，金币总数能被                               n                          n               n 整除。每个人可以给他左右相邻的人一些金币，终极使得每个人的金币数目相当。你的使命是求出被转手的金币数目的最小值。
思绪概述：这题起首还是贪心，但是由于左边和右边都可以给你金币，而且你也可以给别人金币，以是一左一右可以完善抵消掉，那么思绪也就非常简单了，我们不妨假设一个人原有                                        a                         i                                  a_i               ai​ 个金币，给了别人                                        b                         i                                  b_i               bi​ 个金币，那么                                        a                         i                              −                               b                         i                              +                               b                                   i                            −                            1                                       =                      k                          a_i-b_i+b_{i-1}=k               ai​−bi​+bi−1​=k ，                               k                          k               k 的话就是金币总数的均匀值。但是我们是要让                                        b                         i                                  b_i               bi​ 的绝对值最小。那么我们就把这些数值放到数值上，                               ∣                               b                         n                              −                               k                         i                              ∣                          |b_n-k_i|               ∣bn​−ki​∣ 的多少意义，然后再取一个中位数即可。

1. #include<bits/stdc++.h>
2. using namespace std;
3. long long n, g, sum, a[100005], b[100005];
4. int main()
5. {
6.         cin>>n;
7.         for(int i=1;i<=n;i++)
8.         {
9.                 cin>>a[i];
10.                 sum+=a[i];//求和，求平均数
11.         }
12.         g=sum/n;
13.         for(int i=n-1;i;i--)
14.         {
15.                 b[i]=b[i+1]-1LL*(a[i+1]-g);//前缀和记录
16.         }
17.         sort(b+1,b+n+1);
18.         long long mid=(1+n)>>1;
19.         long long ans=0;
20.         for(int i=1;i<=n;i++)
21.         {
22.                 ans+=1LL*abs(b[mid]-b[i]);//取中位数
23.         }
24.         cout<<ans<<endl;
25.         return 0;
26. }

复制代码

细胞分裂

简化题意：将数组中任何一个元素更换为恣意两个和为该元素的数字。将数组酿成元素按非递减序次分列的数组，所需的最少操纵次数。
思绪概述：这道题我以为就是一个贪心加数学的标题，由于标题要求全部操纵事后，除末了一个数外，每个数都不大于后一个数。因此一个数越大，留给前面的数的空间才越多。以是得到贪心结论：末了一个数不拆。
那样根据我们得出的第一个结论，从后往前推，那么不妨设当前这个数字是                               x                          x               x ，它的后一位是                               y                          y               y 。那么久就只有这三种环境。

• 若                                    x                         ≤                         y                              x \leq y                  x≤y ，根据贪心，我们不应该拆分了，已经满意了。
  
• 若                                    x                         >                         y                              x>y                  x>y ，我们必要拆分                                    x                              x                  x 使得拆分后的最大值不凌驾                                    y                              y                  y ，而且根据贪心，拆分后的最小值要尽大概的大，那我们设                                    (                         k                         −                         1                         )                         ×                         y                         <                         x                         ≤                         k                         ×                         y                              (k-1) \times y<x \leq k \times y                  (k−1)×y<x≤k×y （也就是说                                    k                         =                                   ⌈                                       x                               y                                      ⌉                                       k=\left \lceil \frac{x}{y} \right \rceil                  k=⌈yx​⌉），但是我们根据抽屉原理不难过出                                    x                              x                  x 至少要被拆分成                                    k                              k                  k 份，否则最大值肯定会凌驾                                    y                              y                  y 。但是由于拆的次数越少，而且拆的均匀才大概让这个值尽大概地大。因此我们对                                    x                              x                  x 举行                                    (                         k                         −                         1                         )                              (k-1)                  (k−1) 次拆分把它酿成                                    k                              k                  k 个数。此中的最小值呢，就是                                    k                         =                                   ⌊                                       x                               k                                      ⌋                                       k=\left \lfloor \frac{x}{k} \right \rfloor                  k=⌊kx​⌋ 。
  
• 若                                    x                         =                         y                              x=y                  x=y ，什么也不消动，最好的环境。
  

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n;
4. int a[100005];
5. int main()
6. {
7.         cin>>n;
8.         for(int i=1;i<=n;i++)
9.         {
10.                 cin>>a[i];
11.         }
12.         long long ans=0;
13.         int last=a[n];//维护反向枚举中遇到的最小值(包括拆分之后的)
14.         for(int i=n-1;i>0;i--)
15.         {
16.                 if(a[i]>last)
17.                 {
18.                         int cnt=ceil((double)a[i]/last);//一共要分成几个数
19.                         ans+=cnt-1;//统计拆分次数
20.                         last=a[i]/cnt;//切分后的最小值为a[i]/cnt(无论是否能整除)
21.                 }
22.                 else if(a[i]<last)//不需要拆分维护最小值
23.                 {
24.                         last=a[i];
25.                 }
26.                 //剩下的哪一类不用管。
27.         }
28.         cout<<ans<<endl;
29.         return 0;
30. }

复制代码