社区讨论
求助!95分,#9测试的爆WA
P7913[CSP-S 2021] 廊桥分配参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo8e5k10
- 此快照首次捕获于
- 2023/10/27 17:08 2 年前
- 此快照最后确认于
- 2023/10/27 17:08 2 年前
Code in C++
CPP#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100005
#define dMAX(a, b) ((a) > (b) ? (a) : (b))
#define dMIN(a, b) ((a) < (b) ? (a) : (b))
struct Airline // 航班结构体
{
int ari; // 到达时间
int lea; // 离开时间
bool inline operator>(const Airline &) const;
bool inline operator<(const Airline &) const;
};
struct CnvBridge // 廊桥结构体
{
int due; // 当前停靠飞机离开时间
int cnt; // 停靠的飞机总数
CnvBridge(const int &a = 0, const int &b = 0) : due(a), cnt(b) {}
};
int n, m1, m2; // 廊桥个数,国内航班数,国际航班数
Airline dom_f[MAXN], for_f[MAXN]; // 国内航班,国际航班
CnvBridge dom_b[MAXN], for_b[MAXN]; // 国内廊桥,国际廊桥
int dom_sum[MAXN], for_sum[MAXN]; // 前缀和
void input();
void solve();
int read();
int main()
{
freopen("P7913_9.in", "r", stdin);
input();
solve();
// 前缀和处理
dom_sum[0] = 0, for_sum[0] = 0; // 不用0下标
for (int i = 1; i <= m1; i++)
dom_sum[i] = dom_sum[i - 1] + dom_b[i - 1].cnt;
for (int i = 1; i <= m2; i++)
for_sum[i] = for_sum[i - 1] + for_b[i - 1].cnt;
// for (int i = 0; i <= m1; i++)
// cout << dom_sum[i] << ' ';
// cout << endl;
// for (int i = 0; i <= m2; i++)
// cout << for_sum[i] << ' ';
// cout << endl;
int ans = 0;
for (int i = 0; i <= n; i++)
ans = dMAX(ans, dom_sum[i] + for_sum[n - i]);
cout << ans << endl;
return 0;
}
void solve()
{
sort(dom_f, dom_f + m1); // 对国内航班到达时间排序
sort(for_f, for_f + m2); // 对国际航班到达时间排序
for (int i = 0; i < m1; i++) // 模拟国内航班的到达情况
for (int j = 0;; j++) // 枚举国内廊桥,若数据合法,则不会数组越界
{
CnvBridge &cb = dom_b[j];
if (cb.due < dom_f[i].ari) // 如果之前停靠在此廊桥的飞机已经离开
{
cb.due = dom_f[i].lea, cb.cnt++; // 更新当前停靠飞机离开时间和停靠飞机总数
break;
}
}
for (int i = 0; i < m2; i++) // 国际,逻辑同上
for (int j = 0;; j++)
{
CnvBridge &cb = for_b[j];
if (cb.due < for_f[i].ari)
{
cb.due = for_f[i].lea, cb.cnt++;
break;
}
}
// /* Debug - View dom_b[] & for_b[] */
// cout << "国内:" << endl;
// for (int i = 0; i < m1; i++)
// cout << " " << i << ": " << dom_b[i].cnt << endl;
// cout << "国际:" << endl;
// for (int i = 0; i < m2; i++)
// cout << " " << i << ": " << for_b[i].cnt << endl;
}
void input()
{
n = read(), m1 = read(), m2 = read();
for (int i = 0; i < m1; i++)
dom_f[i].ari = read(), dom_f[i].lea = read();
for (int i = 0; i < m2; i++)
for_f[i].ari = read(), for_f[i].lea = read();
}
bool inline Airline::operator>(const Airline &a) const
{
return this->ari > a.ari;
}
bool inline Airline::operator<(const Airline &a) const
{
return this->ari < a.ari;
}
inline int read()
{
int f = 1, r = 0;
char c = getchar();
while (!isdigit(c))
f ^= c == '-', c = getchar();
while (isdigit(c))
r = (r << 1) + (r << 3) + (c & 15), c = getchar();
return f ? r : -r;
}

回复
共 1 条回复,欢迎继续交流。
正在加载回复...