Problem:1098 新建题解

Solution_ID:33070             纯贪心 片段和为零

                   时间复杂度:Θ(O(n)) 空间复杂度:Θ(O(n))

#include <cstdio>

#include <iostream>


using namespace std;


int n, que[105], sum = 0, ans = 0;


int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

{

cin >> que[i];

sum += que[i];

}

int ave = sum / n;

for(int i = 1, sm = 0, cnt = 1; i <= n; i++, cnt++)

{

que[i] -= ave;

sm += que[i];

if(!sm)

{

ans += cnt - 1;

cnt = 0;

}

}

cout << ans << endl;

return 0;

}


by 46068 八月 17, 2019, 2:16 p.m.

Solution_ID:33053            很简单的题目

                   时间复杂度:Θ() 空间复杂度:Θ()

  1. 思路:大家用笔纸简单画一下:从第一个开始,假如前n个的和小于本来该有的值(n*平均数)或者大于 ,
  2. 就必须要并且只需抓牌一次,一次循环到尾即可。






#include <iostream>

#include<vector>

using namespace std;


int main() {

int a;

cin>>a;

vector<int>b;

int sum1=0;

int m;

for(int i=0;i<a;i++){

    cin>>m;

    b.push_back(m);

    sum1+=b[i];

}

sum1=sum1/a;

int sum=0;

int res=0;

for(int i=0;i<a;i++){

    sum=sum+b[i];

    if(sum!=(i+1)*sum1){

        res++;

    }

}

cout<<res<<endl;

return 0;

}


by 93465 八月 14, 2019, 9:06 a.m.

Solution_ID:33043            贪心是会出错的

                   时间复杂度:Θ() 空间复杂度:Θ()

例如下面都没考虑纸牌数不能为负的情况

但谁让人家出到贪心算法里了呢

笑 笑 笑


by 92161 八月 13, 2019, 12:20 a.m.

Solution_ID:33042            一句话,贪心是会出错的

                   时间复杂度:Θ() 空间复杂度:Θ()

但我还不会完全正确的解法

哭  哭  哭 

原谅我只知道问题而不知道解法


by 92161 八月 13, 2019, 12:08 a.m.

Solution_ID:32985            超级简单

                   时间复杂度:Θ() 空间复杂度:Θ()

这里写题解

  1. ```cpp
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<string>
  5. #include<vector>
  6. #include<algorithm>
  7. #include<cstdlib>
  8. #include<cmath>
  9. #include<stack>
  10. #include<map>
  11. using namespace std;

  12. int n,i,x,a[101],ans;

  13. int main()
  14. {
  15.     cin>>n;
  16.     for(i=1;i<=n;i++)
  17.     cin>>a[i];
  18. //a[0]=a[n];
  19. for(i=1;i<=n;i++)
  20. x+=a[i];
  21. x/=n;
  22. for(i=0;i<=n;i++)
  23. a[i]-=x;
  24. for(i=2;i<=n;i++)
  25. {
  26. if(a[i-1]!=0)
  27. a[i]+=a[i-1],ans++;
  28. }
  29. cout<<ans;
  30.     
  31.     
  32.     return 0;
  33. }
  34. ```


by 94029 八月 2, 2019, 7:16 p.m.

Solution_ID:32984            敲简单

                   时间复杂度:Θ() 空间复杂度:Θ()

```cpp

#include<iostream>

#include<cstdio>

#include<string>

#include<vector>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#include<stack>

#include<map>

using namespace std;


int n,i,x,a[101],ans;


int main()

{

    cin>>n;

    for(i=1;i<=n;i++)

    cin>>a[i];

//a[0]=a[n];

for(i=1;i<=n;i++)

x+=a[i];

x/=n;

for(i=0;i<=n;i++)

a[i]-=x;

for(i=2;i<=n;i++)

{

if(a[i-1]!=0)

a[i]+=a[i-1],ans++;

}

cout<<ans;

    

    

    return 0;

}```


by 94029 八月 2, 2019, 7:15 p.m.

Solution_ID:32553            贪心

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<stdio.h>

int main()

{

    int i,n,ave,step=0;

    int sum = 0;

    int a[101];

    scanf("%d",&n);

    for(i=0;i<n;i++)

    {

        scanf("%d",&a[i]);

        sum+=a[i];

    }

    ave = sum/n;

    for(i=0;i<n;i++)

    {

        if(a[i]!=ave)

        {

           a[i+1]+=a[i]-ave;

           step++;

        }

    }

    printf("%d\n",step);

    return 0;

}


by 88798 三月 14, 2019, 6:19 p.m.

Solution_ID:32484            逐个解决法

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <stdio.h>

int n;//纸牌堆数

int poke[100];

int count=0;


void move(int aver,int k)

{

int a;

a=aver - poke[k];

poke[k] += a;

poke[k+1] -= a;

count++;

while(poke[k] == aver)

k++;

if(k < n)

move(aver,k);

}

int main()

{

int i,k;

int aver;

scanf("%d",&n);

for(i=0;i < n;i++)

{

scanf("%d",&poke[i]);

aver+=poke[i];

}

aver=aver/n;

k=n;

for(i=0;i < n;i++)

{

if(poke[i] != aver)

{

k=i;

break;

}

}

if(k < n)

move(aver,k);

printf("%d",count);

return 0;


by 87599 二月 17, 2019, 11:05 p.m.

Solution_ID:32309            将差距一个个丢给后面的堆处理

                   时间复杂度:Θ(O(N)) 空间复杂度:Θ(O(N))

#include <stdio.h>

#include <stdlib.h>


int Input(int Cards[],int N)

{

    int i,Avg=0;

    for(i=0;i<N;i++)

    {

        scanf("%d",&Cards[i]);

        Avg+=Cards[i];

    }

    Avg/=N;

    return Avg;

}


int Count(int Cards[],int N,int Avg)

{

    int i,Gap,Step=0;

    for(i=0;i<N-1;i++)

    {

        Gap=Cards[i]-Avg;

        if(Gap)

        {

            Step++;

            Cards[i]=Avg;

            Cards[i+1]+=Gap;

        }

    }

    return Step;

}


int main()

{

    int Cards[100]={0},N,Avg=0,i,Step;

    scanf("%d",&N);

    Avg=Input(Cards,N);

    Step=Count(Cards,N,Avg);

    printf("%d",Step);

    return 0;

}



by 65190 一月 14, 2019, 9:04 a.m.

Solution_ID:31920            yuqibuertong

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<bits/stdc++.h>
using namespace std;
int main(){
 int n, gun[100], i, tot = 0, count = 0;
 cin >> n;
 for (i=0; i<n; i++){
  cin >> gun[i];
  tot += gun[i];
 }
 tot/=n;
 for (i=0; i<n-1; i++){
  if (gun[i] != tot){
   count++;
   gun[i+1] -= tot - gun[i];
  }
 }
 cout << count;
 return 0;
}


by 79139 九月 28, 2018, 11:10 p.m.

Solution_ID:31654            emmmmmm

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

using namespace std;

int const MAX=101;

int a[MAX];

int main(){

int n,i;

cin>>n;

for(i=1;i<=n;i++) 

cin>>a[i];

int sum=0,k=1;

for(i=1;i<=n;i++){

//if(a[i]>a[k]) k=i;

sum+=a[i];

}

int argv=sum/n;

int ans=0; //计数 

while(1){

for(i=1;i<=n;i++){if(a[i]>a[k]) k=i;} //数组最大 

int sum1=0,sum2=0;

for(i=1;i<k;i++) sum1+=a[i]-argv;

for(i=n;i>k;i--) sum2+=a[i]-argv;

if(a[k]==argv) break;

a[k]=a[k]+sum1+sum2;a[k-1]=a[k-1]-sum1;a[k+1]=a[k+1]-sum2;

if(sum1!=0) ans++; 

if(sum2!=0) ans++;

}

cout<<ans<<endl; 

return 0;


by 51153 八月 11, 2018, 11:11 a.m.

Solution_ID:31531            借鉴前人有趣的想法

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
	int n;
	int a[105];
	int sum = 0;
	int avg, ans = 0;
	cin>>n;
	for(int i = 0; i < n; i++){
		cin>>a[i];
		sum += a[i];
	}
	avg = sum/n;
	for(int i = 0; i < n-1; i++){
		if(a[i] != avg){
			a[i+1] += a[i]-avg; 
			ans++;
		}
	} 
	cout<<ans;
	return 0;
}

by 45761 七月 25, 2018, 4:36 p.m.

Solution_ID:31525            题解

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<bits/stdc++.h>

using namespace std;

#define N 100005

int a[N],n,b,q,ans=0;

int main()

{

cin>>n;

for(int i=1;i<=n;i++)cin>>a[i];

b=a[1];

for(int i=1;i<n;i++)b+=a[i+1];

int x=b/n;

for(int i=1;i<n;i++)

{

if(a[i]<x)

{

q=a[i]-x;

ans++;

a[i+1]+=q;

}

else 

{

if(a[i]>x)

{

q=x-a[i];

ans++;

a[i+1]-=q;

}

}

}

cout<<ans<<endl;

return 0;

}

/*首先把所有牌减去平均数

问题转化为:要从某些正数牌堆把牌移到负数牌堆,使所有牌堆变为0 

再从左往右考虑,若A[i]非零,就让A[i+1]+=A[i],并把ans+1

从1扫到n,最后输出ans即可

↓证明 ↓

若做到i时A[i]>0,就(在最后的方案中)把A[i]张牌移到i+1

若做到i时A[i]<0,就(在最后的方案中)把-A[i]张牌从i+1移到i

若我们不想移动某堆牌i,那么i左边和i右边必定都能自给自足

在这种状态下做到A[i]时它一定=0*/


by 71675 七月 25, 2018, 11:10 a.m.

Solution_ID:31524            题……解……

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<bits/stdc++.h>

using namespace std;

#define N 100005

int a[N],n,b,q,ans=0;

int main()

{

cin>>n;

for(int i=1;i<=n;i++)cin>>a[i];

b=a[1];

for(int i=1;i<n;i++)b+=a[i+1];

int x=b/n;

for(int i=1;i<n;i++)

{

if(a[i]<x)

{

q=a[i]-x;

ans++;

a[i+1]+=q;

}

else 

{

if(a[i]>x)

{

q=x-a[i];

ans++;

a[i+1]-=q;

}

}

}

cout<<ans<<endl;

return 0;

}

/*首先把所有牌减去平均数

问题转化为:要从某些正数牌堆把牌移到负数牌堆,使所有牌堆变为0 

再从左往右考虑,若A[i]非零,就让A[i+1]+=A[i],并把ans+1

从1扫到n,最后输出ans即可

↓证明 ↓

若做到i时A[i]>0,就(在最后的方案中)把A[i]张牌移到i+1

若做到i时A[i]<0,就(在最后的方案中)把-A[i]张牌从i+1移到i

若我们不想移动某堆牌i,那么i左边和i右边必定都能自给自足

在这种状态下做到A[i]时它一定=0*/


by 71675 七月 25, 2018, 11:10 a.m.

Solution_ID:31511            fsuhcikt

                   时间复杂度:Θ() 空间复杂度:Θ()

---------------------------------------------------------------------------------------------------------------------------------

23333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

---------------------------------------------------------------------------------------------------------------------------------

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

...................../´¯/) 
....................,/¯../ 
.................../..../ 
............./´¯/'...'/´¯¯`·¸ 
........../'/.../..../......./¨¯\ 
........('(...´...´.... ¯~/'...') 
.........\.................'...../ 
..........''...\.......... _.·´ 
............\..............( 
..............\.............\

----------------------------------------------------------------------------------------------------------------------------------

23333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

----------------------------------------------------------------------------------------------------------------------------------

/*

作者:yebowen

题目:p1098 均分纸牌

*/


/*

//如何写一份可以提交的代码?以P1000 A+B为例

#include <iostream>

using namespace std;

int main()

{

    int a, b; //定义两个变量名

    cin >> a >> b; //从标准输入流中输入两个整数

    cout << a + b << endl; //输出到标准输出流中


}

// 完成程序以后,点击下方的提交,即可看到测试结果

*/

#include<iostream>


using namespace std;


/*


N堆纸牌,总数是N的倍数


3


3 6 9


*/


int m(int a[],int n)


{


    int max = 0,maxi=0;


    for(int i=0; i<n; i++)


        if(a[i]>max)


        {


            max = a[i];


            maxi = i;


        }


    return maxi;


}




int main(void)


{


    int i,j,k,n;


    while(cin>>n)


    {


        int a[1005],cnt = 0,lneed,rneed,sum=0,ave;


        for(i=0; i<n; i++)


        {


            cin>>a[i];


            sum+=a[i];


        }


        ave = sum/n;


        do


        {


            int maxi = m(a,n);


            lneed=0,rneed=0;


            for(i=0; i<maxi; i++)


                lneed +=(ave-a[i]);


            for(i=n-1; i>maxi; i--)


                rneed += (ave-a[i]);




            if(lneed>0)


            {


                a[maxi-1]+=lneed;


                a[maxi]-=lneed;


                cnt++;


            }


            if(rneed>0)


            {


                a[maxi+1]+=rneed;


                a[maxi]-=rneed;


                cnt++;


            }


        }


        while(lneed||rneed);


        cout<<cnt<<endl;


        }


    return 0;


}


by 78012 七月 24, 2018, 8:48 a.m.

Solution_ID:30684             最笨的方法

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

using namespace std;

/*

N堆纸牌,总数是N的倍数

3

3 6 9

*/

int m(int a[],int n)

{

    int max = 0,maxi=0;

    for(int i=0; i<n; i++)

        if(a[i]>max)

        {

            max = a[i];

            maxi = i;

        }

    return maxi;

}


int main(void)

{

    int i,j,k,n;

    while(cin>>n)

    {

        int a[1005],cnt = 0,lneed,rneed,sum=0,ave;

        for(i=0; i<n; i++)

        {

            cin>>a[i];

            sum+=a[i];

        }

        ave = sum/n;

        do

        {

            int maxi = m(a,n);

            lneed=0,rneed=0;

            for(i=0; i<maxi; i++)

                lneed +=(ave-a[i]);

            for(i=n-1; i>maxi; i--)

                rneed += (ave-a[i]);


            if(lneed>0)

            {

                a[maxi-1]+=lneed;

                a[maxi]-=lneed;

                cnt++;

            }

            if(rneed>0)

            {

                a[maxi+1]+=rneed;

                a[maxi]-=rneed;

                cnt++;

            }

        }

        while(lneed||rneed);

        cout<<cnt<<endl;

        }

    return 0;

}



by 70414 一月 23, 2018, 8:53 p.m.

Solution_ID:30455            纯贪心

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int m[101],n,sum,ans;

int main(){cin>>n;

for(int i=1;i<=n;i++)cin>>m[i],sum+=m[i];sum/=n;

for(int i=1;i*2<=n;i++){

if(m[i]!=sum)ans++;

m[i+1]+=m[i]-sum,m[i]=sum;

if(m[n-i+1]!=sum)ans++;

m[n-i]+=m[n-i+1]-sum,m[n-i+1]=sum;

}cout<<ans;

}


by 24906 十二月 17, 2017, 8:43 p.m.

Solution_ID:30417            懒得优化了

                   时间复杂度:Θ() 空间复杂度:Θ()

#include <cstdio>
#include <cstdlib>
int main(){
    int n,*s=NULL,sum,aver,cnt,flag,i;
    scanf("%d",&n);
    s=(int*)malloc(n*sizeof(int));
    for(i=0,sum=0;i<n;i++) {
        scanf("%d",&s[i]);
        sum+=s[i];    
    }
    aver=sum/n;
    for(i=0;i<n;i++) s[i]-=aver;
    for(i=0,cnt=0,flag=1;i<n-1;i++){
        if(s[i]==0) continue;
        s[i+1]+=s[i];
        cnt++;
    }
    printf("%d\n",cnt);
}


by 69511 十二月 12, 2017, 10:43 p.m.

Solution_ID:30151            贪心是什么?不太懂

                   时间复杂度:Θ() 空间复杂度:Θ()

#include<iostream>

using namespace std;

int main()

{

int n=0;

cin>>n;


int a[110]= {0};

int sum=0;

for(int i=1; i<=n; i++)

{

cin>>a[i];

sum+=a[i];

}

int pingjun=sum/n;

for(int i=1; i<=n; i++)

{

a[i]=a[i]-pingjun;

}


int result=0;

for(int i=1;i<n;i++)

{

if(a[i]!=0)

{

result++;

a[i+1]=a[i+1]+a[i];

a[i]=0;

}

}

cout<<result<<endl;

return 0;

}



by 65329 十一月 12, 2017, 10:41 a.m.

Solution_ID:30004            水爆了

                   时间复杂度:Θ() 空间复杂度:Θ()

var 

  n,i,j,s,s1,ans:longint;

  a:array[1..100] of longint;

begin

  read(n);

  for i:=1 to n do

  begin

    read(a[i]);

    s:=s+a[i];

  end;

  s:=s div n;

  ans:=n;

  for i:=1 to n do

  begin

    inc(s1,a[i]);

    if s1 mod s=0 then dec(ans);

  end;

  write(ans);

end.


by 54948 十一月 4, 2017, 9:08 p.m.