头像

孙锦浩




离线:1个月前


最近来访(55)
用户头像
Misaka_9982
用户头像
kankan
用户头像
zy23
用户头像
水倾文
用户头像
Naive_512
用户头像
翔翔翔翔
用户头像
misaka_mikoto
用户头像
Big_Tortoise
用户头像
CipherTri
用户头像
奇怪的章北海又跑路了
用户头像
Misaka御坂
用户头像
Jackyc
用户头像
樱花飞舞
用户头像
fanh
用户头像
Avakos
用户头像
李林成
用户头像
xjc008
用户头像
Коммунистический
用户头像
昊天无极
用户头像
Xinqwq

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

孙锦浩
1个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

int n;
priority_queue <int, vector <int>, greater <int> > heap;
int ans;

int main()
{
    scanf("%d", &n);
    while (n --)
    {
        int v;
        cin >> v;
        heap.push(v);
    }

    while (heap.size() > 1)
    {
        auto a = heap.top();

        heap.pop();

        auto b = heap.top();

        heap.pop();

        ans += (a + b);

        heap.push(a + b);
    }

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

    return 0;
}


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

孙锦浩
1个月前
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
typedef pair <int, int> pii;

const int N = 5e4 + 10;
int n;
pii num[N];
int ans = -1e9;

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

    sort(num, num + n);

    for (int i = 0, sum = 0; i < n; i ++)
    {
        int w = num[i].y;
        int s = num[i].x - w;
        ans = max(ans, sum - s);
        sum += w;
    }

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

    return 0;
}


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

孙锦浩
1个月前
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int n;
int num[N];
int sum;
ll ans;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &num[i]);

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

    int sum = num[n + 1 >> 1];

    for (int i = 1; i <= n; i++) ans += abs(num[i] - sum);

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

    return 0;
}


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

孙锦浩
1个月前
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int n;
int num[N];
ll ans;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &num[i]);

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

    for (int i = 1; i <= n - 1; i ++) ans += num[i] * (n - i);

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

    return 0;
}


活动打卡代码 AcWing 906. 区间分组

孙锦浩
1个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n;

struct Range
{
    int l, r;
    bool operator <(const Range& W) const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }

    sort(range, range + n);

    priority_queue <int, vector <int>, greater <int> > heap;

    for (int i = 0; i < n; i ++)
    {
        auto r = range[i];

        if (heap.empty() || heap.top() >= r.l) heap.push(r.r);
        else
        {
            heap.pop();
            heap.push(r.r);
        }
    }

    cout << heap.size() << endl;

    return 0;
}



孙锦浩
1个月前
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;
#define x first
#define y second

int n;
vector <pii> interval;
int ed = -1e9 - 10;
int ans;

bool cmp(pii a, pii b)
{
    return a.y < b.y;
}

int main()
{
    cin >> n;
    while (n --)
    {
        int l, r;
        cin >> l >> r;

        interval.push_back({l, r});
    }

    sort(interval.begin(), interval.end(), cmp);

    for (auto item : interval)
    {
        if (ed < item.x)
        {
            ans ++;
            ed = item.y;
        }
    }

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 907. 区间覆盖

孙锦浩
1个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n;
bool success = false;
int ans;

struct Range
{
    int l, r;
    bool operator < (const Range& W) const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int st, ed;
    cin >> st >> ed;
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int l, r;
        cin >> l >> r;
        range[i] = {l, r};
    }

    sort(range, range + n);

    for (int i = 0; i < n; i++)
    {
        int j = i;
        int r = -2e9;

        while (j < n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j ++;
        }
        if (r < st)
        {
            ans = -1;

            break;
        }

        ans ++;

        if (r >= ed)
        {
            success = true;

            break;
        }

        st = r;
        i = j - 1;
    }

    if (! success) ans = -1;

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 1140. 最短网络

孙锦浩
1个月前
#include<bits/stdc++.h>

using namespace std;

const int N = 110;
int g[N][N];
int n;
int dist[N];
bool str[N];

int prim()
{
    int res = 0;

    memset(dist, 0x3f, sizeof dist);

    dist[1]=0;

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

        for (int j = 1; j <= n; j ++) if (! str[j] && (t == -1 || dist[t] > dist[j])) t=j;

        res += dist[t];
        str[t] = true;

        for (int j = 1; j <= n; j ++) if (dist[j] > g[t][j]) dist[j] = g[t][j];
    }

    return res;
}

int main()
{
    cin >> n;

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

    cout << prim() << endl;

    return 0;
}


活动打卡代码 AcWing 2681. 聪明的猴子

孙锦浩
1个月前
#include <bits/stdc++.h>

using namespace std;

int m, n;
int ans;
int x[1005], y[1005];
double a[1005];
double sum;

double d(int a, int b, int c, int d)
{
    double x = c - a, y = d - b;
    return sqrt(x * x + y * y);
}

int p[1000010];

struct Edge
{
    int a, b;
    double w;
    Edge(int a, int b)
    {
        this -> a = a;
        this -> b = b;

        w = d(x[a], y[a], x[b], y[b]);
    }

    Edge() { }

    bool operator < (const Edge &W) const
    {
        return w < W.w;
    }
}edges[1000010];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);

    return p[x];
}
void kruskal()
{
    sort(edges + 1, edges + ans + 1);

    for (int i = 1; i <= ans; i ++) p[i] = i;
    for (int i = 1; i <= ans; i ++)
    {
        int a = find(edges[i].a), b = find(edges[i].b);

        if (a != b)
        {
            p[a] = b;
            sum = max(sum, edges[i].w);
        }
    }
}

int main()
{
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> a[i];
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];

        for (int j = 1; j <= i; j ++)
            edges[++ ans] = Edge(i, j);
    }

    kruskal();

    ans = 0;

    for (int i = 1; i <= m; i ++) if (a[i] >= sum) ans ++;

    cout << ans << endl;

    return 0;
}


活动打卡代码 AcWing 346. 走廊泼水节

孙锦浩
1个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 100;
int fa[N];
int n, m;
int k, t;
int s[N];
long long ans;

struct node
{
    int x, y, w;
}edge[N];

bool cmp(node a, node b)
{
    return a.w < b.w;
}
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main()
{
    scanf("%d\n", &t);

    while (t --)
    {
        scanf("%d\n", &n);

        for (int i = 1; i < n; i ++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
        for (int i = 1; i <= n; i ++)
        {
            fa[i] = i;
            s[i] = 1;
        }

        sort(edge + 1, edge + n, cmp);

        ans = 0;

        for (int i = 1;i < n;i ++)
        {
            int x = find(edge[i].x);
            int y = find(edge[i].y);
            int w = edge[i].w;

            if (x == y) continue;

            ans += (long long)(s[x] * s[y] - 1) * (w + 1);
            fa[x] = y;
            s[y] += s[x];
        }

        printf("%lld\n",ans);
    }

    return 0;
}