头像

Godlessness




离线:6天前



class MinStack {
public:
    /** initialize your data structure here. */
    //建立两个栈,一个记录数值,一个记录最小值
    stack<int> value;
    stack<int> MIN;
    MinStack() {

    }

    void push(int x) {
        value.push(x);
        if(MIN.empty()||x<=MIN.top())
        {
            MIN.push(x);
        }
    }

    void pop() {
        if(value.top()==MIN.top())
        {
            MIN.pop();
        }
        value.pop();
    }

    int top() {
        return value.top();
    }

    int getMin() {
        return MIN.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */


活动打卡代码 AcWing 126. 最大的和

#include<iostream>
#include<algorithm>
using namespace std;

const int N=110;
int a[N][N];
int sum[N][N];
int res=-1e9;
int n;

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[i][j]);
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
            }

    //枚举边界
    for(int i=1;i<=n;i++)//上边界
        for(int j=i;j<=n;j++)//下边界
        {
            int temp=0;

            for(int k=1;k<=n;k++)
            {
                temp+=sum[j][k]-sum[j][k-1]-sum[i-1][k]+sum[i-1][k-1];

                res=max(temp,res);
                if(temp<0) temp=0;

            }
        }

    cout<<res<<endl;

    return 0;
}


活动打卡代码 AcWing 125. 耍杂技的牛

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> PII;
const int N=5e4+10;
PII cows[N];
int n;
LL wcow[N];

int main()
{
    cin>>n;

    for(int i=0;i<n;i++) 
    {
        LL w,s;
        scanf("%lld%lld",&w,&s);
        cows[i].first=w+s;
        cows[i].second=s;
    } 

    sort(cows,cows+n);

    LL sum=0,mindan=-1e9;
    for(int i=0;i<n;i++)
    {
        wcow[i]=cows[i].first-cows[i].second;
        sum+=wcow[i];
        mindan=max(mindan,sum-wcow[i]-cows[i].second);
    }

    cout<<mindan<<endl;

    return 0;
}


活动打卡代码 AcWing 116. 飞行员兄弟

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int g[5][5];

void operation()
{
    int ans,time=1e9,k;

    for(k=0;k<1<<16;k++)
    {
        int res=0;
        int back[5][5];
        memcpy(back,g,sizeof g);

        for(int i=0;i<16;i++)
        {
            if(k>>i&1)
            {
                res++;
                int x,y;

                if(i==0||i==4||i==8||i==12) y=1;
                else if(i==1||i==5||i==9||i==13) y=2;
                else if(i==2||i==6||i==10||i==14) y=3;
                else y=4;
                x=i/4+1;

                for(int j=1;j<=4;j++) g[x][j]^=1;
                for(int j=1;j<=4;j++) 
                {
                    if(j!=x)
                    g[j][y]^=1;
                }
            }
        }    

        int p,q;
        bool flag=true;
        for(p=1;p<=4;p++)
        for(q=1;q<=4;q++)
        {
            if(g[p][q]==1) flag=false;
        }   
        if(flag==true)
        {
            if(time>res)
            {
                time=res;
                ans=k;
            }
        }

        memcpy(g,back,sizeof back);
    }

    cout<<time<<endl;
    for(int i=0;i<16;i++)
    {
        if(ans>>i&1)
            {
                int x,y;

                if(i==0||i==4||i==8||i==12) y=1;
                else if(i==1||i==5||i==9||i==13) y=2;
                else if(i==2||i==6||i==10||i==14) y=3;
                else y=4;
                x=i/4+1;

                cout<<x<<" "<<y<<endl;
            }
    }
}

int main()
{
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            {
                char t;
                cin>>t;
                if(t=='+') g[i][j]=1;
                else g[i][j]=0;
            }

    operation();

    return 0;
}


活动打卡代码 AcWing 112. 雷达设备

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

typedef pair<double,double> PDD;
const int N=1010;
int n,d;
PDD ioslate[N];

int main()
{
    cin>>n>>d;
    bool flag=true;

    for(int i=0;i<n;i++) 
    {
        int x,y;
        scanf("%d%d",&x,&y);

        if(y>d) 
        {
            flag=false;
            break;
        }

        double D=sqrt(d*d-y*y);
        ioslate[i].first=x-D;
        ioslate[i].second=x+D;
    }

    sort(ioslate,ioslate+n);

    if(flag==false)
    {
        cout<<-1;
        return 0;
    }

    int cnt=0;
    double pos=-1e9;
    for(int i=0;i<n;i++)
    {
        if(pos<ioslate[i].first)
        {
            pos=ioslate[i].second;
            cnt++;
        }
        else pos=min(pos,ioslate[i].second);//重点
    }

    cout<<cnt;
    return 0;
}


活动打卡代码 AcWing 111. 畜栏预定

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N=5e4+10;
pair<PII,int> cow[N];
int n;
int id[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)  
    {
        scanf("%d%d",&cow[i].first.first,&cow[i].first.second);
        cow[i].second=i;
    }

    sort(cow,cow+n);

    priority_queue<PII,vector<PII>,greater<PII>>heap;
    for(int i=0;i<n;i++)
    {
        if(heap.empty()||heap.top().first>=cow[i].first.first)
        {
            PII stall;//记录每个区间的右端点
            stall={cow[i].first.second,heap.size()+1};
            id[cow[i].second]=stall.second;
            heap.push(stall);
        }
        else
        {
            auto stall=heap.top();
            heap.pop();
            id[cow[i].second]=stall.second;
            stall.first=cow[i].first.second;
            heap.push(stall);
        }
    }

    cout<<heap.size()<<endl;
    for(int i=0;i<n;i++) printf("%d\n",id[i]);
    return 0;
}


活动打卡代码 AcWing 110. 防晒

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

typedef pair<int,int> PII;
const int N=2510;
int c,l;
PII spf[N];
int res;

int main()
{
    map<int,int>cover;
    cin>>c>>l;
    for(int i=0;i<c;i++) cin>>spf[i].first>>spf[i].second;
    for(int i=0;i<l;i++) 
    {
        int a,b;
        scanf("%d%d",&a,&b);
        cover[a]+=b;
    }

    sort(spf,spf+c);

    for(int i=c-1;i>=0;i--)
    {
       for(int j=spf[i].second;j>=spf[i].first;j--)
       {
           if(cover[j]>0)
           {
               cover[j]--;
               res++;
               break;
           }
       }
    }

    cout<<res;
    return 0;
}


活动打卡代码 AcWing 106. 动态中位数

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;

int main()
{
    int p;
    cin>>p;

    while(p--)
    {
        //定义大根堆
        //less表示按照从小到大顺序插入元素
        priority_queue<int,vector<int>,less<int>>bigheap;
        //定义小根堆
        //greater表示按照从大到小顺序插入元素
        priority_queue<int,vector<int>,greater<int>>smallheap;

        int num,n,cnt=0;
        scanf("%d%d",&num,&n);
        printf("%d %d\n",num,(n+1)/2);

        for(int i=1;i<=n;i++)
        {
            int number;
            scanf("%d",&number);

            if(bigheap.empty()||number<bigheap.top()) bigheap.push(number);
            else smallheap.push(number);

            if(bigheap.size()>smallheap.size()+1) 
            {
                int t=bigheap.top();
                bigheap.pop();
                smallheap.push(t);
            }

            if(smallheap.size()>bigheap.size())
            {
                int t=smallheap.top();
                bigheap.push(t);
                smallheap.pop();
            }


            if(i&1) 
            {
                cout<<bigheap.top();
                cnt++;
                if(cnt%10==0)cout<<endl;
                else cout<<" ";
            }
        }
        if(cnt%10!=0) printf("\n");
    }

    return 0;
}



活动打卡代码 AcWing 107. 超快速排序

//求逆序对数量
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

typedef long long LL;
const int N=5e5+10;
int q[N];
LL num;

LL merge_sort(int l,int r)//归并排序
{
    if(l==r) return 0;

    int mid=(l+r)/2;
    num=merge_sort(l,mid)+merge_sort(mid+1,r);

    int tmp[N];
    int i=l,j=mid+1,cnt=0;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) tmp[cnt++]=q[i++];
        else 
        {
            tmp[cnt++]=q[j++];
            num=num+mid-i+1;
        }
    }

    while(i<=mid) tmp[cnt++]=q[i++];
    while(j<=r) tmp[cnt++]=q[j++];

    for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];

    return num;
}

int main()
{
    int n;

    while(scanf("%d",&n)&&n!=0)
    {
        num=0;//记录逆序对个数

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

        cout<<merge_sort(0,n-1)<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 103. 电影

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<map>
using namespace std;

const int N=2e5+10;
int lanuage[N];
map<int,int>num;//各个数没有大小之间的联系,所以可以用map存储
struct scients
{
    int voice;
    int word;
}mm[N];
int n,m;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&lanuage[i]);
        num[lanuage[i]]++;
    }
    cin>>m;
    for(int i=1;i<=m;i++) scanf("%d",&mm[i].voice);
    for(int i=1;i<=m;i++) scanf("%d",&mm[i].word);

    int choose=1;
    int happya=0;
    for(int i=1;i<=m;i++)//语音
    {
        if(num[mm[i].voice]>happya)
        {
            happya=num[mm[i].voice];
            choose=i;
        }
    }

    int happyb=0;
    for(int i=1;i<=m;i++)//字幕
    {
        if(num[mm[i].voice]==happya)
        {
            if(num[mm[i].word]>happyb)
            {
                choose=i;
                happyb=num[mm[i].word];
            }
        }
    }

    cout<<choose;
    return 0;
}