头像

yxc

北京大学


访客:1319815

离线:6小时前


活动打卡代码 AcWing 1571. 完美序列

yxc
8小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, p;
int a[N];

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

    sort(a, a + n);

    int res = 0;
    for (int i = 0, j = 0; i < n; i ++ )
    {
        while ((long long)a[j] * p < a[i]) j ++ ;
        res = max(res, i - j + 1);
    }

    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 1530. 最短距离

yxc
8小时前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int s[N];

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

    scanf("%d", &m);
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        if (l > r) swap(l, r);
        printf("%d\n", min(s[r - 1] - s[l - 1], s[n] - s[r - 1] + s[l - 1]));
    }

    return 0;
}


活动打卡代码 AcWing 1506. 中位数

yxc
8小时前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 200010;

int n, m;
int a[N], b[N], c[N * 2];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);

    int k = 0, i = 0, j = 0;
    while (i < n && j < m)
        if (a[i] <= b[j]) c[k ++ ] = a[i ++ ];
        else c[k ++ ] = b[j ++ ];
    while (i < n) c[k ++ ] = a[i ++ ];
    while (j < m) c[k ++ ] = b[j ++ ];

    printf("%d\n", c[(n + m - 1) / 2]);

    return 0;
}


活动打卡代码 AcWing 1626. 链表元素分类

yxc
8小时前
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 100010;

int n, k;
int h, e[N], ne[N];

int main()
{
    scanf("%d%d%d", &h, &n, &k);
    for (int i = 0; i < n; i ++ )
    {
        int address, key, next;
        scanf("%d%d%d", &address, &key, &next);
        e[address] = key, ne[address] = next;
    }

    vector<int> a, b, c;
    for (int i = h; i != -1; i = ne[i])
    {
        int v = e[i];
        if (v < 0) a.push_back(i);
        else if (v <= k) b.push_back(i);
        else c.push_back(i);
    }

    a.insert(a.end(), b.begin(), b.end());
    a.insert(a.end(), c.begin(), c.end());

    for (int i = 0; i < a.size(); i ++ )
    {
        printf("%05d %d ", a[i], e[a[i]]);
        if (i + 1 == a.size()) puts("-1");
        else printf("%05d\n", a[i + 1]);
    }

    return 0;
}



yxc
8小时前
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 100010;

int n;
int h, e[N], ne[N];
bool st[N];

int main()
{
    scanf("%d%d", &h, &n);
    for (int i = 0; i < n; i ++ )
    {
        int address, key, next;
        scanf("%d%d%d", &address, &key, &next);
        e[address] = key, ne[address] = next;
    }

    vector<int> a, b;
    for (int i = h; i != -1; i = ne[i])
    {
        int v = abs(e[i]);
        if (st[v]) b.push_back(i);
        else
        {
            st[v] = true;
            a.push_back(i);
        }
    }

    for (int i = 0; i < a.size(); i ++ )
    {
        printf("%05d %d ", a[i], e[a[i]]);
        if (i + 1 == a.size()) puts("-1");
        else printf("%05d\n", a[i + 1]);
    }
    for (int i = 0; i < b.size(); i ++ )
    {
        printf("%05d %d ", b[i], e[b[i]]);
        if (i + 1 == b.size()) puts("-1");
        else printf("%05d\n", b[i + 1]);
    }

    return 0;
}


活动打卡代码 AcWing 1560. 反转链表

yxc
9小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n, m;
int h, e[N], ne[N];

int main()
{
    scanf("%d%d%d", &h, &n, &m);

    for (int i = 0; i < n; i ++ )
    {
        int address, data, next;
        scanf("%d%d%d", &address, &data, &next);
        e[address] = data, ne[address] = next;
    }

    vector<int> q;
    for (int i = h; i != -1; i = ne[i]) q.push_back(i);

    for (int i = 0; i + m - 1 < q.size(); i += m)
        reverse(q.begin() + i, q.begin() + i + m);

    for (int i = 0; i < q.size(); i ++ )
    {
        printf("%05d %d ", q[i], e[q[i]]);
        if (i + 1 == q.size()) puts("-1");
        else printf("%05d\n", q[i + 1]);
    }

    return 0;
}


活动打卡代码 AcWing 1516. 共享

yxc
9小时前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n;
int h1, h2, ne[N];
char e[N];
bool st[N];

int main()
{
    scanf("%d%d%d", &h1, &h2, &n);
    for (int i = 0; i < n; i ++ )
    {
        int address, next;
        char data;
        scanf("%d %c %d", &address, &data, &next);
        e[address] = data, ne[address] = next;
    }

    for (int i = h1; i != -1; i = ne[i])
        st[i] = true;

    for (int i = h2; i != -1; i = ne[i])
        if (st[i])
        {
            printf("%05d\n", i);
            return 0;
        }

    puts("-1");

    return 0;
}


活动打卡代码 AcWing 1517. 是否加满油

yxc
9小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int c_max, d, d_avg, n;
struct Stop
{
    double p, d;

    bool operator< (const Stop& t) const
    {
        return d < t.d;
    }
}s[N];

int main()
{
    cin >> c_max >> d >> d_avg >> n;
    for (int i = 0; i < n; i ++ ) cin >> s[i].p >> s[i].d;
    s[n] = {0, (double)d};

    sort(s, s + n + 1);

    if (s[0].d)
    {
        puts("The maximum travel distance = 0.00");
        return 0;
    }

    double res = 0, oil = 0;
    for (int i = 0; i < n;)
    {
        int k = -1;
        for (int j = i + 1; j <= n && s[j].d - s[i].d <= c_max * d_avg; j ++ )
            if (s[j].p < s[i].p)
            {
                k = j;
                break;
            }
            else if (k == -1 || s[j].p < s[k].p)
                k = j;

        if (k == -1)
        {
            printf("The maximum travel distance = %.2lf\n", s[i].d + (double)c_max * d_avg);
            return 0;
        }

        if (s[k].p <= s[i].p)
        {
            res += ((s[k].d - s[i].d) / d_avg - oil) * s[i].p;
            i = k;
            oil = 0;
        }
        else
        {
            res += (c_max - oil) * s[i].p;
            oil = c_max - (s[k].d - s[i].d) / d_avg;
            i = k;
        }
    }

    printf("%.2lf\n", res);

    return 0;
}


活动打卡代码 AcWing 1618. 结绳

yxc
9小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
double a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a, a + n);

    for (int i = 1; i < n; i ++ ) a[0] = (a[0] + a[i]) / 2;

    printf("%d\n", (int)a[0]);

    return 0;
}


活动打卡代码 AcWing 1603. 整数集合划分

yxc
10小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

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

    int s1 = 0, s2 = 0;
    for (int i = 0; i < n / 2; i ++ ) s1 += a[i];
    for (int i = n / 2; i < n; i ++ ) s2 += a[i];

    printf("%d %d\n", n % 2, s2 - s1);

    return 0;
}