Codeforces 967 贪心服务器分配资源 线性基XOR递增序列构造
2024-09-01 18:54:33
A
#include<bits/stdc++.h>
using namespace std;
int dir[][] = {{, -}, {, }, { -, }, {, }};
typedef long long ll;
int n, s;
int h[];
int m[];
int num[];
int getans(int h1, int m1, int h2, int m2)
{
int x1 = (h2 - h1) * ;
int x2 = m2 - m1;
return x1 + x2;
}
int main()
{
//freopen("out.txt", "w", stdout);
cin >> n >> s;
for (int i = ; i <= n; i++)
{
cin >> h[i] >> m[i];
}
if (h[] * + m[] >= + s)
{
cout << << " " << << endl;
return ;
}
for (int i = ; i <= n - ; i++)
{
int now = getans(h[i], m[i], h[i + ], m[i + ]);
if (now >= s * + )
{
m[i]++;
m[i] += s;
while(m[i] >= )
{
m[i] -= ;
h[i]++;
}
cout << h[i] << " " << m[i] << endl;
return ;
}
}
m[n]++;
m[n] += s;
while (m[n] >= )
{
m[n] -= ;
h[n]++;
}
cout << h[n] << " " << m[n] << endl;
}
B
#include<bits/stdc++.h>
using namespace std;
int dir[][] = {{, -}, {, }, { -, }, {, }};
typedef long long ll;
int n;
ll a, b;
ll s[];
ll sum = ;
priority_queue<int, vector<int>, less<int> >que;
int main()
{
//freopen("out.txt", "w", stdout);
cin >> n >> a >> b;
for (int i = ; i <= n; i++)
{
cin >> s[i];
sum += s[i];
if (i != )
{
que.push(s[i]);
}
}
int anser = ;
if (s[]*a >= b * sum)
{
cout << << endl;
return ;
}
int flag = ;
while (flag)
{
sum -= que.top();
que.pop();
anser++;
if (s[]*a >= b * sum)
{
cout << anser << endl;
return ;
}
}
}
C
注意判定同楼层的情况
#include<bits/stdc++.h>
using namespace std;
int dir[][] = {{, -}, {, }, { -, }, {, }};
typedef long long ll;
ll l[];
ll e[];
ll n, m, cl, ce, v;
ll x1, y1, x2, y2;
ll anser = ;
ll addx, addy;
int main()
{
//freopen("out.txt", "w", stdout);
cin >> n >> m >> cl >> ce >> v;
for (int i = ; i <= cl; i++)
{
cin >> l[i];
}
sort(l + , l + cl + );
for (int i = ; i <= ce; i++)
{
cin >> e[i];
}
sort(e + , e + ce + );
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 + , l + cl + , y1) - l - ;
//cout<<" "<<now<<endl;
int lef = max(now - , );
int rig = min(now + , (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 + , l + cl + , y2) - l - ;
lef = max(now - , );
rig = min(now + , (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 + , e + ce + , y1) - e - ;
lef = max(now - , );
rig = min(now + , (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 + , e + ce + , y2) - e - ;
lef = max(now - , );
rig = min(now + , (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;
}
}
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 - ; i > ; i--)
{
int p = lower_bound(c + , c + n + , a[i]) - c; //如果选x1作为前面连续的一部分 分为i份所需要开始的最前位置
int ps = p + i - ; //分成i份后的末尾部分
if (ps < n && b[n - ps] <= c[ps + ]) //如果作为前面一部分成立 并且把x2分成n-ps份后所需的资源数小于c[ps+1] 整体成立
{
puts("Yes");
printf("%d %d\n", i, n - ps);
for (int i = p; i <= ps; i++)
{
printf("%d ", id[i]);
}
puts("");
for (int i = ps + ; i <= n; i++)
{
printf("%d ", id[i]);
}
exit();
}
}
}
void solve2() //作用同上
{
for (int i = n - ; i > ; i--)
{
int p = lower_bound(c + , c + n + , b[i]) - c, ps = p + i - ;
if (ps < n && a[n - ps] <= c[ps + ])
{
puts("Yes");
printf("%d %d\n", n - ps, i);
for (int i = ps + ; i <= n; i++)
{
printf("%d ", id[i]);
}
puts("");
for (int i = p; i <= ps; i++)
{
printf("%d ", id[i]);
}
exit();
}
}
}
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 = ; i <= n; i++)
{
scanf("%d", &c[i]), id[i] = i;
}
sort(id + , id + n + , cmp); //相当于sort piar<int,int>
sort(c + , c + n + );
for (int i = ; i <= n; i++)
{
a[i] = x1 / i + (x1 % i > ), b[i] = x2 / i + (x2 % i > );
//a[i] 表示如果x1平均分为i个所需要的资源数
//b[i] 表示如果x2平均分为i个所需要的资源数
}
solve1();
solve2();
puts("No");
return ;
}
E
最新文章
- MyEclipse10安装Svn插件的几种方法
- STM32F4读写内部FLASH【使用库函数】
- Java File类总结和FileUtils类
- 3.7---猫狗收容所（CC150）
- MyEclipse破解(MEGen.java)
- 设置ASP.NET页面的运行超时时间详细到单个页面及站点
- 原生javascript里jsonp的实现原理
- 部署应用程序脚本+GUIRunOnce命令
- 【最大流】ECNA 2015 F Transportation Delegation (Codeforces GYM 100825)
- 命运（HDU 2571 简单动态规划）
- java编辑器
- jenkins+gitlab自动化编译部署方案探索及服务端编译webpack实战
- 近期编程总结（i think -1）
- Mathematica求微分换元
- JavaScript作用域(第七天)
- C语言之二维数组与指针
- python面向对象三大特性之一继承、多态、封装
- oracle-sql内置函数
- 如何在Oracle中 查询一个表被其他数据库对象引用[z]
- NSObject常用方法和反射