头像

一抹斜阳


访客:2286

离线:2天前



#include <iostream>
using namespace std;

const int N= 1e5 + 10;
int a[N];
int n;
int res ;
void cnt(int x){

    res = 0;
    while(x){

        if(x & 1 == 1)
            res++;
        x = x >> 1;
    }
    printf("%d ",res);

}
int main(){


    cin>>n;
    for(int i = 0;i<n;i++){
        scanf("%d",&a[i]);
        cnt(a[i]);
    }

    return 0;

}



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

开始第一遍写的时候开的s[N]和w[N]拿两个都排序后结果算
后来想到要整体排序,两对不能拆开


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

const int N = 5e4 + 10;
int n;
struct Cattle{

    int w;
    int s;

    bool operator < (const Cattle &c) const{

        return w + s < c.s + c.w;
    }
}cattle[N];

int main(){

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

        scanf("%d",&cattle[i].w);
        scanf("%d",&cattle[i].s);
    }

    sort(cattle,cattle + n);

    long long res = -1e18 ,sum = 0;
    for(i = 0;i<n;i++){

        res = max(res,sum - cattle[i].s);
        sum += cattle[i].w ;

    }

    cout<<res<<endl;
    return 0;
}





活动打卡代码 AcWing 844. 走迷宫

一抹斜阳
2个月前
#include <iostream>
#include <queue>

using namespace std;
const int N = 110;
int maze[N][N];
bool used[N][N];
int bfs();
int n,m;

struct point
{
    int x,y;
    int d;
    point(int a,int b,int c)
    {
        x = a;
        y = b;
        d = c;
    }

};

int main()
{

    cin>>n>>m;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
        {
            scanf("%d",&maze[i][j]);
        }
    cout<<bfs()<<endl;
    return 0;
}

int bfs()
{
    queue<point> q;

    q.push(point(1,1,0));
    //used[1][1] = true;

    while(!q.empty())
    {

        point p = q.front();


        if(p.x == n && p.y == m)
            return p.d;
        else
        {
            if((p.y -1 >=1 ) && (!used[p.x][p.y - 1]) && (maze[p.x][p.y-1] == 0) )
            {
                q.push(point(p.x,p.y-1,p.d + 1));
                used[p.x][p.y-1] = true;
            }

            if((p.y +1 <= m) && (!used[p.x][p.y + 1]) && (maze[p.x][p.y+1] == 0) )
            {
                q.push(point(p.x,p.y+1,p.d + 1));
                used[p.x][p.y+1] = true;
            }

            if((p.x +1 <= n) && (!used[p.x + 1][p.y]) && (maze[p.x+1][p.y] == 0) )
            {
                q.push(point(p.x+1,p.y,p.d + 1));
                used[p.x+1][p.y] = true;
            }

            if((p.x -1 >=1) && (!used[p.x - 1][p.y]) && (maze[p.x-1][p.y] == 0) )
            {
                q.push(point(p.x-1,p.y,p.d + 1));
                used[p.x-1][p.y] = true;
            }
        }

        q.pop();

    }
}


活动打卡代码 AcWing 104. 货仓选址

一抹斜阳
2个月前
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 1e5 + 10;
int a[N];
long long res;

int main()
{
    int n;
    cin>>n;
    for(int i = 0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    int location = n >> 1;

    for(int i = 0;i<n;i++)
    {
        res += abs(a[i] - a[location]);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 913. 排队打水

一抹斜阳
2个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int a[N];
int n;
long long res;



int main()
{

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

    sort(a,a + n);
    int wait = 0;
    for(int i = 1;i<n;i++)
    {
        wait += a[i-1];
        res += wait;
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

一抹斜阳
2个月前
#include <iostream>
#include <algorithm>
#include <functional>
#include <queue>

using namespace std;

int n;
long long res;
priority_queue<int ,vector<int>,greater<int> > pq;

int main()
{
    cin>>n;
    int x = 0;
    while(n--)
    {

        scanf("%d",&x);
        pq.push(x);
    }

    while(pq.size() > 1)
    {
        int x = pq.top();
        pq.pop();
        int y = pq.top();
        pq.pop();
        pq.push(x + y);
        res += x + y;

    }

    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1235. 付账问题

一抹斜阳
2个月前
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std; 

const int N = 5e5 + 10;
int a[N];
int n;
int s;

int main()
{

    cin>>n>>s;
    for(int i= 0;i<n;i++ )
    {
        scanf("%d",&a[i]);
    }

    double avg = 1.0*s/n;
    double changeAvg = avg;
    double sum = 0;
    sort(a,a+n);

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

        if(changeAvg > a[i])
        {
            s -= a[i];
            sum += (avg - a[i]) * (avg - a[i]) ;
            changeAvg = 1.0 * s / (n - i - 1);
        }
        else 
            sum += (changeAvg - avg) * (changeAvg - avg); 
    }
    printf("%.4lf", sqrt(sum / n));
    return  0;
}



一抹斜阳
3个月前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;
struct Range
{
    int l,r;
    bool operator <(const Range &range) const 
    {
        if(this->r<range.r)
            return true;
        return false;
    }
};

Range range[N];
int n;

int main()
{

    int res = 0;
    cin>>n;
    for(int i = 1;i<=n;i++)
        scanf("%d%d",&range[i].l,&range[i].r);

    sort(range + 1,range + n + 1);
    int end = -1e9;
    for(int i = 1;i <= n;i++)
    {
        if(range[i].l > end)
        {
            ++res;
            end = range[i].r;
        }

    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 905. 区间选点

一抹斜阳
3个月前
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;
struct Range
{
    int l,r;
    bool operator <(const Range &range) const 
    {
        if(this->r<range.r)
            return true;
        return false;
    }
};

Range range[N];
int n;

int main()
{

    int res = 0;
    cin>>n;
    for(int i = 1;i<=n;i++)
        scanf("%d%d",&range[i].l,&range[i].r);

    sort(range + 1,range + n + 1);
    int end = -1e9;
    for(int i = 1;i <= n;i++)
    {
        if(range[i].l > end)
        {
            ++res;
            end = range[i].r;
        }

    }
    cout<<res<<endl;
    return 0;
}



一抹斜阳
3个月前
//类似于分糖果
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m,t;
int x[N];
int y[N];
int row[N];
int column[N];
long long c[N];

int main()
{

    cin>>n>>m>>t;
    for(int i = 1;i <= t;i++)
    {
        scanf("%d",&x[i]);
        scanf("%d",&y[i]);
        row[x[i]]++;
        column[y[i]]++;

    }

    if((t % n !=0) && (t % m != 0))
    {
        printf("impossible\n");
    }
    else if(t % n != 0)
    {
        int avg = t/m;
        for(int i = 2;i<=m;i++)
        {

            c[i] = c[i-1] + avg -column[i];

        }

        sort(c+1,c+m+1);
        long long coun = 0;
        int k = 1 + m >>1;
        for(int i = 1;i <= m;i++)
        {
            coun += abs(c[k] - c[i]);
        }

        cout<<"column "<<coun<<endl;
    }
    else if(t %m != 0)
    {
        int avg = t/n;
        for(int i = 2;i<=n;i++)
        {

            c[i] = c[i-1] + avg -row[i];

        }

        sort(c+1,c+n+1);
        long long coun = 0;
        int k = 1 + n >>1;
        for(int i = 1;i <= n;i++)
        {
            coun += abs(c[k] - c[i]);
        }

        cout<<"row "<<coun<<endl;
    }
    else
    {

        int avg = t/m;
        for(int i = 2;i<=m;i++)
        {

            c[i] = c[i-1] + avg -column[i];

        }

        sort(c+1,c+m+1);
        long long coun1 = 0;
        int k = 1 + m >>1;
        for(int i = 1;i <= m;i++)
        {
            coun1 += abs(c[k] - c[i]);
        }

        for(int i = 1;i<=m;i++)
        {
            c[i] = 0;
        }

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

            c[i] = c[i-1] + avg -row[i];

        }

        sort(c+1,c+n+1);
        long long coun2 = 0;
        k = 1 + n >>1;
        for(int i = 1;i <= n;i++)
        {
            coun1 += abs(c[k] - c[i]);
        }
        long long coun = coun1 + coun2;
        cout<<"both "<<coun<<endl;
    }
    return 0;
}