2020年八月月赛题解五道题（没有思路，只有代码）

题目1：传送窗

题目2：传送窗

题目3：传送窗

题目4：传送窗

题目5：传送窗

题目1：

#include<bits/stdc++.h>

using namespace std;

int main(){

    int n,m;

    cin>>n>>m;

    int nums[n+2];

    int t=0;

    int ans=1;

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

        cin>>nums[i];

        if(t+nums[i]>m){

            ans++;

            t=nums[i];

        }

        else{

            t+=nums[i];

        }

    }

    cout<<ans;

    return 0;

}

题目2：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<utility>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<map>

#include<bitset>

#define EPS 1e-9

#define PI acos(-1.0)

#define INF 0x3f3f3f3f

#define LL long long

const int MOD = 1E9+7;

const int N = 1000000+5;

const int dx[] = {-1,1,0,0,-1,-1,1,1};

const int dy[] = {0,0,-1,1,-1,1,-1,1};

using namespace std;

struct Line{

    int x,y;

    bool operator < (const Line &rhs)const{

        return y<rhs.y;

    }

}line[N];

int main(){

    int n;

    scanf("%d",&n);

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

        scanf("%d%d",&line[i].x,&line[i].y);

    sort(line+1,line+1+n);

    int res=1;

    int temp=line[1].y;

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

        if(line[i].x>=temp){

            temp=line[i].y;

            res++;

        }

    }

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

    return 0;

}

题目三：

#include<bits/stdc++.h>

#define N 1000010

using namespace std;

int f[N];

int n,flag;

struct node

{

    int e,s;

}eg[N];

bool cmp(node x,node y)

{

    if(x.s==y.s)

        return x.e<y.e;

    return x.s>y.s;

}

void init()

{

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

        f[i]=i;

}

int check(int x)

{

    if(x<=0)

        return x;

    else if(x==f[x])

    {

        f[x]=x-1;

        flag=1;

        return f[x];

    }

    else return f[x]=check(f[x]);

}

int main()

{

    init();

    scanf("%d",&n);

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

        scanf("%d%d",&eg[i].e,&eg[i].s);

    sort(eg,eg+n,cmp);

    int ans=0;

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

    {

        flag=0;

        f[eg[i].e]=check(eg[i].e);

        if(flag)ans+=eg[i].s;

    }

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

} 

题目4：

#include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int N = 110;

 int dis[N],n,h;

struct Node {

     int Fish , Dec ;

     bool operator < ( const Node & rhs ) const {

         return Fish < rhs.Fish ;

     }

 }a[N];

 int main()

 {

     scanf("%d%d",&n,&h);

     for (int i=1;i<=n;i++) scanf("%d",&a[i].Fish);

     for (int i=1;i<=n;i++) scanf("%d",&a[i].Dec);

     for (int i=2;i<=n;i++) scanf("%d",&dis[i]);

     h *= 12 ;

     int sum = 0 , ans = 0 ;

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

         h -= dis[i] ;

         sum = 0 ;

         priority_queue < Node > q ;

         for ( int j = 1 ; j <= i ; j++ ){

             q.push ( a[j] ) ;

         }

         int time = h ;

         while ( time > 0 ){

             Node cur = q.top() ;

             q.pop() ;

             if( cur.Fish <= 0 )

                 break ;

             sum += cur.Fish ;

             time -- ;

             cur.Fish -= cur.Dec;

             q.push(cur);

         }

         ans = max ( ans , sum ) ;

    }

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

     return 0;

 }

题目5：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e6+10;

ll a[N],s[N],c[N];

int n;

int main()

{

    cin>>n;

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

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

    int avg=s[n]/n;

    c[1]=0;

    for(int i=2;i<=n;i++)  c[i]=c[i-1]+a[i]-avg;

    sort(c+1,c+1+n);

    ll res=0;

    for(int i=1;i<=n;i++) res+=abs(c[i]-c[(n+1)/2]);

    cout<<res<<endl;

}