P1007. 独木桥
两个士兵相遇转身继续行走可视为相向继续行走
一个在loc[i]的士兵到独木桥两端所需时间分别为loc[i]、len+1-loc[i]
最少的通过时间，通过求出每人到两边所需的最小时间，取所有人中耗时最长的人所用的时间
最多的通过时间，通过求出每人到两边所需的最大时间，取所有人中耗时最长的人所用的时间
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int len, n;
int loc[5010];
int minn = 0, maxx = 0;
cin >> len >> n;
for (int i = 1; i <= n; i ++) {
cin >> loc[i];
}
for (int i = 1; i <= n; i ++) {
minn = max(minn, min(loc[i], len + 1 - loc[i]));
maxx = max(maxx, max(loc[i], len + 1 - loc[i]));
}
cout << minn << " " << maxx;
return 0;
}P1031. [NOIP2002 提高组] 均分纸牌
纸牌的平均数即为最终每个牌堆数
从左向右遍历，当前牌堆纸牌数不为平均数，需要将多的牌数分给下个牌堆或将缺的牌数从下个牌堆拿取，并使操作数加一
#include<iostream>
using namespace std;
int main()
{
int n,a[105];
int level = 0;
int step = 0;
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> a[i];
level += a[i];
}
level /= n;
for (int i = 1; i < n; i ++) {
if (a[i] != level) {
a[i + 1] += a[i] - level;
step ++;
}
}
cout << step;
return 0;
}
P2695. 骑士的工作
头的大小和zi都进行从小到大排序，使用优先队列操作
从第一个数开始比较zi是否大于等于头的大小
zi大于等于头的大小，则将zi计入花费，两指针均后移一位比较下一组值
zi小于头的大小，则将zi指针后移直到其大于等于头的大小，若zi指针先到底，则失败
如果失败，指向头的大小指针不会到底，要么头的数目比z数目多，要么z的大小不满足条件而使指针提前到底
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > head;
priority_queue<int, vector<int>, greater<int> > z;
int main()
{
int n, m;
int k;
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
cin >> k;
head.push(k);
}
for (int i = 1; i <= m; i ++) {
cin >> k;
z.push(k);
}
int money = 0;
while (!head.empty() && !z.empty()) {
if (head.top() <= z.top()) {
money += z.top();
head.pop();
z.pop();
}
else {
z.pop();
}
}
if (!head.empty()) {
cout << "you died!";
}
else {
cout << money;
}
return 0;
}P5639. 【CSGRound2】守序者的尊严
通过一段相同开关情况的路灯时间为1
遇到不一样的开关情况路灯就加1
第一个监控一定关闭，不需要额外判断时间是否加1
#include <iostream>
using namespace std;
int n, m, k;
int sum = 1;
int main()
{
cin >> n >> k;
while (-- n) {
cin >> m;
if (m != k) {
sum ++;
}
k = m;
}
cout << sum;
return 0;
}P1056. [NOIP2008 普及组] 排座椅
要隔开一对说话的同学，如果他们在一行，则取他们所在两列的较小值，如果他们在一列，则取他们所在两行的较小值
使用结构体数组a[i]、b[j]分别记录在i行、j列设置通道所能隔开说话同学的对数以及所在行或列的位置
最多设置k行l列通道，分别通过循环先将隔开说话同学对数降序排列，在根据行列将其对应k行、l列升序排列
#include <iostream>
#include <algorithm>
using namespace std;
struct SetLine {
int num;
int loc;
};
bool cmpNum(SetLine a, SetLine b) {
return a.num > b.num;
}
bool cmpLoc(SetLine a, SetLine b) {
return a.loc < b.loc;
}
SetLine a[1010], b[1010];
int m, n, k, l, d;
int x, y, p, q;
int main()
{
cin >> m >> n >> k >> l >> d;
while (d --) {
cin >> x >> y >> p >> q;
if (x != p) {
a[min(x, p)].num ++;
a[min(x, p)].loc = min(x, p);
}
else if (y != q) {
b[min(y, q)].num ++;
b[min(y, q)].loc = min(y, q);
}
}
sort(a + 1, a + 1 + m, cmpNum);
sort(b + 1, b + 1 + n, cmpNum);
sort(a + 1, a + 1 + k, cmpLoc);
sort(b + 1, b + 1 + l, cmpLoc);
for (int i = 1; i <= k; i ++) {
cout << a[i].loc << " ";
}
cout << "\n";
for (int i = 1; i <= l; i ++) {
cout << b[i].loc << " ";
}
return 0;
}P1090. [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
每次选取果子数目最少的两堆合并
使用优先队列，让果堆的果子数目按从小到大排列，每次拿取并移除前两个果堆，总和计入体力耗费，新的果堆的果子数目为两堆之和，再把该堆加入优先队列
每次取出的两个果堆要是所有果堆中果子数目最小的两个果堆
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > a;
int n, m;
int x, y;
int sum;
int main()
{
cin >> n;
while (n --) {
cin >> m;
a.push(m);
}
while (a.size() > 1) {
x = a.top();
a.pop();
y = a.top();
a.pop();
sum += x + y;
a.push(x + y);
}
cout << sum;
return 0;
}P1106. 删数问题
从左到右依次删去较大的数，即当前位的数若比后一位的数大，将当前位数删除
在k大于0下进行上述操作，直到k为0或指针扫描到最后一位
k如果仍大于0，此时数据满足从左到右不递减排序，从右开始依次删除即可
可能存在有前导零的情况，需忽略这些输出
#include <iostream>
#include <cstring>
using namespace std;
string n;
int k;
int a[255];
int loc, len;
int main()
{
cin >> n >> k;
len = n.length();
for (int i = 0; i < len; i ++) {
a[i + 1] = n[i] - '0';
}
loc = 1;
while (loc < len && k) {
if (a[loc] > a[loc + 1]) {
for (int i = loc; i < len; i ++) {
a[i] = a[i + 1];
}
k --;
loc --;
len --;
}
else {
loc ++;
}
}
if (k) len -= k;
loc = 1;
while (!a[loc] && loc < len) {
loc ++;
}
for (int i = loc; i <= len; i ++) {
cout << a[i];
}
return 0;
}[]P4779. 【模板】单源最短路径（标准版）
[]P2240. 【深基12.例1】部分背包问题
金币可以随意分割，计算每堆金币的单位价格，从高价到低价依次放入背包
若背包足以放下一堆金币，则全部放入
若背包不足以放下一堆金币，则把背包放满并加上对应价值
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Coin {
int m;
int v;
double p;
};
Coin c[105];
int n, t;
double value;
int weight;
int idx;
bool cmp(Coin a, Coin b) {
return a.p > b.p;
}
int main()
{
cin >> n >> t;
for (int i = 1; i <= n; i ++) {
cin >> c[i].m >> c[i].v;
c[i].p = c[i].v * 1.0 / c[i].m;
}
sort(c + 1, c + 1 + n, cmp);
while (idx <= n) {
idx ++;
if (t - weight >= c[idx].m) {
weight += c[idx].m;
value += c[idx].v;
}
else {
value += c[idx].p * (t - weight);
break;
}
}
printf("%.2lf", value);
return 0;
}P2630. 图像变换
操作的顺序不影响结果，所有操作最终可简化为八种操作中的一种，或无解
操作：A、B、C、D、AA、AB、AC、AD
可用色纸模拟
#include <iostream>
using namespace std;
int a[10], b[10];
int main()
{
cin >> a[1] >> a[2] >> a[3] >> a[4] >> a[5] >> a[6] >> a[7] >> a[8] >> a[9];
cin >> b[1] >> b[2] >> b[3] >> b[4] >> b[5] >> b[6] >> b[7] >> b[8] >> b[9];
if (a[1] == b[3] && a[2] == b[6] && a[3] == b[9] && a[4] == b[2] && a[5] == b[5] && a[6] == b[8] && a[7] == b[1] && a[8] == b[4] && a[9] == b[7]) cout << "A";
else if (a[1] == b[7] && a[2] == b[4] && a[3] == b[1] && a[4] == b[8] && a[5] == b[5] && a[6] == b[2] && a[7] == b[9] && a[8] == b[6] && a[9] == b[1]) cout << "B";
else if (a[1] == b[3] && a[2] == b[2] && a[3] == b[1] && a[4] == b[6] && a[5] == b[5] && a[6] == b[4] && a[7] == b[9] && a[8] == b[8] && a[9] == b[7]) cout << "C";
else if (a[1] == b[7] && a[2] == b[8] && a[3] == b[9] && a[4] == b[4] && a[5] == b[5] && a[6] == b[6] && a[7] == b[1] && a[8] == b[2] && a[9] == b[3]) cout << "D";
else if (a[1] == b[9] && a[2] == b[8] && a[3] == b[7] && a[4] == b[6] && a[5] == b[5] && a[6] == b[4] && a[7] == b[3] && a[8] == b[2] && a[9] == b[1]) cout << "AA";
else if (a[1] == b[1] && a[2] == b[2] && a[3] == b[3] && a[4] == b[4] && a[5] == b[5] && a[6] == b[6] && a[7] == b[7] && a[8] == b[8] && a[9] == b[9]) cout << "AB";
else if (a[1] == b[1] && a[2] == b[4] && a[3] == b[7] && a[4] == b[2] && a[5] == b[5] && a[6] == b[8] && a[7] == b[3] && a[8] == b[6] && a[9] == b[9]) cout << "AC";
else if (a[1] == b[9] && a[2] == b[6] && a[3] == b[3] && a[4] == b[8] && a[5] == b[5] && a[6] == b[2] && a[7] == b[7] && a[8] == b[4] && a[9] == b[1]) cout << "AD";
else cout << "Poland cannot into space!!!";
return 0;
}P5514. [MtOI2019] 永夜的报应
a ^ b <= a + b，两数异或的值不会比其和大
表面上要求分组，实际上将所有数异或即为最优解
#include <iostream>
using namespace std;
int n, x;
int ans;
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> x;
ans ^= x;
}
cout << ans;
return 0;
}P3619. 魔法
T在任何时候都需要大于0，否则直接不能完成任务
要完成一个任务，需要T>t，完成后T变为T+b
将任务分成两组，一组b>0，一组b<0
在b>0时按照所需t从小到大依次完成（b=0也可在此处理）
在b<0时，若出现完成任务1后不能完成任务2，但先完成任务2可以完成任务1，即T+b1<t2，T+b2>t1，化简得 t1+b1<t2+b2，按照t和b的和从大到小依次完成
#include <iostream>
#include <algorithm>
using namespace std;
struct Task {
int t;
int b;
};
bool cmpx(Task x, Task y) {
return x.t < y.t;
}
bool cmpy(Task x, Task y) {
return x.t + x.b > y.t + y.b;
}
Task magicx[100010];
Task magicy[100010];
long long T;
int Z, n;
int t, b;
int nx, ny;
int f;
int main()
{
cin >> Z;
while (Z --) {
nx = ny = 0;
f = 0;
cin >> n >> T;
for (int i = 1; i <= n; i ++) {
cin >> t >> b;
if (b > 0) {
nx ++;
magicx[nx].t = t;
magicx[nx].b = b;
}
else {
ny ++;
magicy[ny].t = t;
magicy[ny].b = b;
}
}
sort(magicx + 1, magicx + 1 + nx, cmpx);
sort(magicy + 1, magicy + 1 + ny, cmpy);
for (int i = 1; i <= nx; i ++) {
if (T > magicx[i].t) {
T += magicx[i].b;
}
else {
f = 1;
break;
}
}
if (f) {
cout << "-1s\n";
continue;
}
for (int i = 1; i <= ny; i ++) {
if (T > magicy[i].t) {
T += magicy[i].b;
}
else {
f = 1;
break;
}
}
if (f || T <= 0) {
cout << "-1s\n";
continue;
}
cout << "+1s\n";
}
return 0;
}题目描述
Comments | NOTHING