526互联

7.17作业

发布时间 2023-07-16 21:36:40作者: o-Sakurajimamai-o
// 1.数列分段 Section I
//用last记录前面总和不小于m的值,如果当前值+last>m,说明last区间的为一组,然后开一个新的组
//时间复杂度o(n)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m,last=-1;
bool vis[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    // cin>>t;
    // while(t--){        
    // }
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>t;
        if(last==-1){
            last=t;
            continue;
        }
        if(i>=1&&last+t>m) res++,last=t;
        else if(last+t<=m) last+=t;
    }
    cout<<res+1<<endl;
    return 0;
}

//2.凌乱的yyy / 线段覆盖
//按区间左端点排序,就是一个区间覆盖问题,和建立雷达类似
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num=-1,ans,m;
bool vis[N];
struct node
{
    int l,r;
    bool operator<(const node&w)const
    {
        return r<w.r;
    }
}op[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++) cin>>op[i].l>>op[i].r;
    sort(op,op+n);
    for(int i=0;i<n;i++) if(op[i].l>=num) res++,num=op[i].r;
    cout<<res<<endl;
    return 0;
}

//3.合并果子
//每次都合并最小的果子,这样得到的体力值才是最小的,因为你如果先把大的放进去
//之后的操作每次都要加一次,会越来越多
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    // cin>>t;
    // while(t--){ 
    // }
    cin>>n;
    priority_queue<int,vector<int>,greater<int>>heap;
    for(int i=0;i<n;i++) cin>>m,heap.push(m);
    while(heap.size()>1){
        int a=heap.top();heap.pop();
        int b=heap.top();heap.pop();
        res+=(a+b);
        heap.push(a+b);
    }
    res+=heap.top();
    cout<<res<<endl;
    return 0;
}

//4.排队接水
//用结构体记录序号和需要的接水时间,然后排个序就可以
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
struct node
{
    int id,shijian;
    bool operator<(const node&w)const
    {
        return shijian<w.shijian;
    }
}p[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    // cin>>t;
    // while(t--){
    // }
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i].shijian,p[i].id=i;
    sort(p+1,p+n+1);
    double res=0.00;
    for(int i=1;i<=n;i++) cout<<p[i].id<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++) a[i]=a[i-1]+p[i].shijian;
    for(int i=1;i<=n-1;i++) res+=a[i];
    printf("%.2lf",(double)res/n);
    return 0;
}

//5.小A的糖果
//模拟
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i>1&&a[i-1]+a[i]>m) res+=a[i-1]+a[i]-m,a[i]=m-a[i-1];
    }
    cout<<res;
    return 0;
}

//6.跳跳！
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a,a+n+1);
    int st=0,last=n;
    while(st<last){
        res+=(a[last]-a[st])*(a[last]-a[st]); ++st;
        res+=(a[last]-a[st])*(a[last]-a[st]); --last;
    }
    cout<<res;
    return 0;
}

//7.陶陶摘苹果（升级版）
//只需要排序体力即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int n,t,a,b,s,res,num,ans,m;
bool vis[N];
struct node
{
    int x,y;
    bool operator<(const node&w)const
    {
        return y<w.y;
    }
}p[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>s>>a>>b;
    for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y;
    sort(p,p+n);
    for(int i=0;i<n;i++){
        if(p[i].x<=a+b&&p[i].y<=s) res++,s-=p[i].y;
        if(s<=0) break;
    }
    cout<<res<<endl;
    return 0;
}

//8.[USACO1.3] 混合牛奶 Mixing Milk
//正常排序就可以做
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
struct node
{
    int price,l;
    bool operator<(const node&w)const{
        return price<w.price; 
    }
}p[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>m>>n;
    for(int i=0;i<n;i++) cin>>p[i].price>>p[i].l;
    sort(p,p+n); 
    for(int i=0;i<n;i++){
        if(m>=p[i].l) res+=p[i].price*p[i].l,m-=p[i].l;
        else if(m>0&&m<p[i].l) res+=p[i].price*m,m=0;
        if(m<=0) break;
    }
    cout<<res;
    return 0;
}

//9.选数
//dfs,运用欧拉筛进行筛;
//三个状态,现在的位置,现在的总和,现在的次数
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m,prime[N];
bool vis[N],st[N];
void dfs(int now,int num,int cnt)
{
    if(now>n) return;
    if(cnt==m){
        if(!vis[num]) res++;
        return;
    }
    for(int i=now+1;i<=n;i++) dfs(i,num+a[i],cnt+1);
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    vis[0]=vis[1]=true;
    for(int i=2;i<=N;i++){
        if(!vis[i]) prime[++num]=i;
        for(int j=1;prime[j]<=N/i;j++){
            vis[prime[j]*i]=true;
            if(!(i%prime[j])) break;
        }
    }
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(0,0,0);
    cout<<res<<endl;
    return 0;
}

//10.kkksc03考前临时抱佛脚
//暴力搜索,每次选左边或者右边,直到选完
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
int n,t,a[N],res,num,ans,m,l,r,s[5];
bool vis[N];
void dfs(int now,int i)
{
    if(now>s[i]){
        ans=min(ans,max(l,r));
        return;
    }
    l+=a[now]; dfs(now+1,i),l-=a[now],r+=a[now],dfs(now+1,i),r-=a[now];
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>s[1]>>s[2]>>s[3]>>s[4];
    for(int i=1;i<=4;i++){
        ans=0x3f3f3f,l=0,r=0;
        for(int j=1;j<=s[i];j++) cin>>a[j];
        dfs(1,i);
        res+=ans;
    }
    cout<<res;
    return 0;
}

//11.「EZEC-5」修改数组
//所有的1就是答案
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],res,num,ans,m;
bool vis[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        bool f=false;
        ans=0,res=0,num=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(a[i]==1) res++;
        }
        cout<<res<<endl;
        for(int i=0;i<n;i++){
            if(a[i]==1) f=true;
            if(f) cout<<1<<" ";
            else cout<<0<<" ";
        }
        cout<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],res,num,ans,m;
bool vis[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        bool f=false;
        ans=0,res=0,num=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(a[i]==1) res++;
        }
        cout<<res<<endl;
        for(int i=0;i<n;i++){
            if(a[i]==1) f=!f,cout<<1<<" ";
            if(a[i]==0&&f) cout<<1<<" ";
            else if(a[i]==0&&!f) cout<<0<<" ";
        }
        cout<<endl;
    }
    return 0;
}