您的位置: 首页  >  IT文章  >  Codeforces 967 贪心服务器分配资源 线性基XOR递增序列构造

Codeforces 967 贪心服务器分配资源 线性基XOR递增序列构造

分类: IT文章 • 2023-11-07 23:38:31

A

#include<bits/stdc++.h>
using namespace std;
int dir[4][2] = {{0, -1}, {0, 1}, { -1, 0}, {1, 0}};
typedef long long ll;
int n, s;
int h[105];
int m[105];
int num[1000005];
int getans(int h1, int m1, int h2, int m2)
{
        int x1 = (h2 - h1) * 60;
        int x2 = m2 - m1;
        return x1 + x2;
}
int main()
{
        //freopen("out.txt", "w", stdout);
        cin >> n >> s;
        for (int i = 1; i <= n; i++)
        {
                cin >> h[i] >> m[i];
        }
        if (h[1] * 60 + m[1] >= 1 + s)
        {
                cout << 0 << " " << 0 << endl;
                return 0;
        }
        for (int i = 1; i <= n - 1; i++)
        {
                int now = getans(h[i], m[i], h[i + 1], m[i + 1]);
                if (now >= s * 2 + 2)
                {
                        m[i]++;
                        m[i] += s;
                        while(m[i] >= 60)
                        {
                                m[i] -= 60;
                                h[i]++;
                        }
                        cout << h[i] << " " << m[i] << endl;
                        return 0;
                }
        }
        m[n]++;
        m[n] += s;
        while (m[n] >= 60)
        {
                m[n] -= 60;
                h[n]++;
        }
        cout << h[n] << " " << m[n] << endl;
}
View Code

B

#include<bits/stdc++.h>
using namespace std;
int dir[4][2] = {{0, -1}, {0, 1}, { -1, 0}, {1, 0}};
typedef long long ll;
int n;
ll a, b;
ll s[100005];
ll sum = 0;
priority_queue<int, vector<int>, less<int> >que;
int main()
{
        //freopen("out.txt", "w", stdout);
        cin >> n >> a  >> b;
        for (int i = 1; i <= n; i++)
        {
                cin >> s[i];
                sum += s[i];
                if (i != 1)
                {
                        que.push(s[i]);
                }
        }
        int anser = 0;
        if (s[1]*a >= b * sum)
        {
                cout << 0 << endl;
                return 0;
        }
        int flag = 1;
        while (flag)
        {
                sum -= que.top();
                que.pop();
                anser++;
                if (s[1]*a >= b * sum)
                {
                        cout << anser << endl;
                        return 0;
                }
        }
}
View Code

C

注意判定同楼层的情况

#include<bits/stdc++.h>
using namespace std;
int dir[4][2] = {{0, -1}, {0, 1}, { -1, 0}, {1, 0}};
typedef long long ll;
ll l[100005];
ll e[100005];
ll n, m, cl, ce, v;
ll x1, y1, x2, y2;
ll anser = 0;
ll addx, addy;
int main()
{
        //freopen("out.txt", "w", stdout);
        cin >> n >> m >> cl >> ce >> v;
        for (int i = 1; i <= cl; i++)
        {
                cin >> l[i];
        }
        sort(l + 1, l + cl + 1);
        for (int i = 1; i <= ce; i++)
        {
                cin >> e[i];
        }
        sort(e + 1, e + ce + 1);
        int q;
        cin >> q;
        while (q--)
        {
                anser = INT_MAX;
                cin >> x1 >> y1 >> x2 >> y2;
                if (x1 == x2)
                {
                        cout << abs(y1 - y2) << endl;
                        continue;
                }
                if (y1 > y2)
                {
                        swap(x1, x2);
                        swap(y1, y2);
                }
                addy = abs(x1 - x2);
                int now = lower_bound(l + 1, l + cl + 1, y1) - l - 1;
                //cout<<"   "<<now<<endl;
                int lef = max(now - 2, 1);
                int rig = min(now + 2, (int)cl);
                //cout << lef << "  l1  " << rig << endl;
                for (int i = lef; i <= rig; i++)
                {
                        addx = abs(l[i] - y1) + abs(l[i] - y2);
                        anser = min(anser, addx + addy);
                }
                now = lower_bound(l + 1, l + cl + 1, y2) - l - 1;
                lef = max(now - 2, 1);
                rig = min(now + 2, (int)cl);
                //cout << lef << "  l2  " << rig << endl;
                for (int i = lef; i <= rig; i++)
                {
                        addx = abs(l[i] - y1) + abs(l[i] - y2);
                        anser = min(anser, addx + addy);
                }
                addy = abs(x1 - x2) / v;
                if (addy * v < abs(x1 - x2))
                {
                        addy++;
                }
                now = lower_bound(e + 1, e + ce + 1, y1) - e - 1;
                lef = max(now - 2, 1);
                rig = min(now + 2, (int)ce);
                //cout << lef << "  e1  " << rig << endl;
                for (int i = lef; i <= rig; i++)
                {
                        addx = abs(e[i] - y1) + abs(e[i] - y2);
                        anser = min(anser, addx + addy);
                }
                now = lower_bound(e + 1, e + ce + 1, y2) - e - 1;
                lef = max(now - 2, 1);
                rig = min(now + 2, (int)ce);
                //cout << lef << "  e2  " << rig << endl;
                for (int i = lef; i <= rig; i++)
                {
                        addx = abs(e[i] - y1) + abs(e[i] - y2);
                        anser = min(anser, addx + addy);
                }
                cout << anser << endl;
        }
}
View Code

D

卡题意 总共有两个任务 分别需要X1 X2的资源

你有N个服务器 每个服务器上只能运行一个任务 但是你可以把任务平分到几个服务器上运行 问你能不能完成这两个任务

肯定先排序 然后这两个任务各所在的服务器肯定是连续的一段

预处理出每个任务分成i份所需要的资源 枚举哪个任务所在服务器是前面的 然后再枚举这个任务分成几份 check第二个任务是否能满足

能满足就输出

#include<bits/stdc++.h>
#define maxn 300005
using namespace std;
int a[maxn], b[maxn], c[maxn], id[maxn], n;
void solve1()
{
        for (int i = n - 1; i > 0; i--)
        {
                int p = lower_bound(c + 1, c + n + 1, a[i]) - c;  //如果选x1作为前面连续的一部分 分为i份所需要开始的最前位置
                int ps = p + i - 1;  //分成i份后的末尾部分
                if (ps < n && b[n - ps] <= c[ps + 1])  //如果作为前面一部分成立 并且把x2分成n-ps份后所需的资源数小于c[ps+1] 整体成立
                {
                        puts("Yes");
                        printf("%d %d
", i, n - ps);
                        for (int i = p; i <= ps; i++)
                        {
                                printf("%d ", id[i]);
                        }
                        puts("");
                        for (int i = ps + 1; i <= n; i++)
                        {
                                printf("%d ", id[i]);
                        }
                        exit(0);
                }
        }
}
void solve2() //作用同上
{
        for (int i = n - 1; i > 0; i--)
        {
                int p = lower_bound(c + 1, c + n + 1, b[i]) - c, ps = p + i - 1;
                if (ps < n && a[n - ps] <= c[ps + 1])
                {
                        puts("Yes");
                        printf("%d %d
", n - ps, i);
                        for (int i = ps + 1; i <= n; i++)
                        {
                                printf("%d ", id[i]);
                        }
                        puts("");
                        for (int i = p; i <= ps; i++)
                        {
                                printf("%d ", id[i]);
                        }
                        exit(0);
                }
        }
}
bool cmp(const int &A, const int &B)
{
        return c[A] < c[B];
}
int main()
{
        int x1, x2;
        scanf("%d%d%d", &n, &x1, &x2);
        for (int i = 1; i <= n; i++)
        {
                scanf("%d", &c[i]), id[i] = i;
        }
        sort(id + 1, id + n + 1, cmp);  //相当于sort piar<int,int>
        sort(c + 1, c + n + 1);
        for (int i = 1; i <= n; i++)
        {
                a[i] = x1 / i + (x1 % i > 0), b[i] = x2 / i + (x2 % i > 0);
                //a[i] 表示如果x1平均分为i个所需要的资源数
                //b[i] 表示如果x2平均分为i个所需要的资源数
        }
        solve1();
        solve2();
        puts("No");
        return 0;
}
View Code

E

相关推荐