简答题 偏难
#22120

1、廊桥分配

1、廊桥分配


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;bits/stdc++.h&gt; using namespace std; const int Maxn = 1e5 + 5; struct e {     int st, ed; } a[Maxn]; bool cmp(e x, e y) {     return x.st &lt; y.st; } priority_queue&lt;int&gt; hp_id; priority_queue&lt;pair&lt;int, int&gt;&gt; hp_ed; int n, m1, m2, ca[Maxn], cb[Maxn]; int main() {     scanf("%d%d%d", &amp;n, &amp;m1, &amp;m2);          for (int i = 1; i &lt;= m1; ++i) {         scanf("%d%d", &amp;a[i].st, &amp;a[i].ed);     }          sort(a + 1, a + m1 + 1, cmp);          for (int i = 1; i &lt;= n; ++i) {         hp_id.push(-i);     }          for (int i = 1; i &lt;= m1; ++i) {         if (!hp_ed.empty()) {             while (-hp_ed.top().first &lt; a[i].st) {                 hp_id.push(-hp_ed.top().second);                 hp_ed.pop();                 if (hp_ed.empty()) {                     break;                 }             }         }                  if (!hp_id.empty()) {             int x = -hp_id.top();             hp_id.pop();             ca[x]++;             hp_ed.push(make_pair(-a[i].ed, x));         }     }          for (int i = 1; i &lt;= n; ++i) {         ca[i] += ca[i - 1];     }          while (!hp_ed.empty()) {         hp_ed.pop();     }     while (!hp_id.empty()) {         hp_id.pop();     }          for (int i = 1; i &lt;= m2; ++i) {         scanf("%d%d", &amp;a[i].st, &amp;a[i].ed);     }          sort(a + 1, a + m2 + 1, cmp);          for (int i = 1; i &lt;= n; ++i) {         hp_id.push(-i);     }          for (int i = 1; i &lt;= m2; ++i) {         if (!hp_ed.empty()) {             while (-hp_ed.top().first &lt; a[i].st) {                 hp_id.push(-hp_ed.top().second);                 hp_ed.pop();                 if (hp_ed.empty()) {                     break;                 }             }         }                  if (!hp_id.empty()) {             int x = -hp_id.top();             hp_id.pop();             cb[x]++;             hp_ed.push(make_pair(-a[i].ed, x));         }     }          for (int i = 1; i &lt;= n; ++i) {         cb[i] += cb[i - 1];     }          int mx_ans = 0;     for (int i = 0; i &lt;= n; ++i) {         mx_ans = max(mx_ans, ca[i] + cb[n - i]);     }          printf("%d", mx_ans);          return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include &lt;bits/stdc++.h&gt; using namespace std; // 计算某类航班(国内或国际)分配bridgeNum个廊桥时,能停靠的最大飞机数 int countPlanes(vector&lt;pair&lt;int, int&gt;&gt;&amp; flights, int bridgeNum) {     if (bridgeNum == 0) return 0;     sort(flights.begin(), flights.end()); // 按到达时间升序排序     // used: 存储(离开时间, 廊桥编号),小根堆(按离开时间排序,便于释放过期廊桥)     priority_queue&lt;pair&lt;int, int&gt;, vector&lt;pair&lt;int, int&gt;&gt;, greater&lt;&gt;&gt; used;     // idle: 存储空闲廊桥编号,小根堆(便于分配最小编号的空闲廊桥)     priority_queue&lt;int, vector&lt;int&gt;, greater&lt;&gt;&gt; idle;     for (int i = 1; i &lt;= bridgeNum; ++i) {         idle.push(i);     }     int res = 0;     for (auto&amp; flight : flights) {         int arrTime = flight.first, depTime = flight.second;         // 释放所有离开时间 &lt;= 当前航班到达时间的廊桥(将这些廊桥加入空闲队列)         while (!used.empty() &amp;&amp; used.top().first &lt;= arrTime) {             idle.push(used.top().second);             used.pop();         }         // 若有空闲廊桥,分配给当前航班         if (!idle.empty()) {             int bridgeId = idle.top();             idle.pop();             used.push({depTime, bridgeId});             res++;         }     }     return res; } int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     int n, m1, m2;     cin &gt;&gt; n &gt;&gt; m1 &gt;&gt; m2;     vector&lt;pair&lt;int, int&gt;&gt; domestic, international;     // 读取国内航班信息     for (int i = 0; i &lt; m1; ++i) {         int a, b;         cin &gt;&gt; a &gt;&gt; b;         domestic.emplace_back(a, b);     }     // 读取国际航班信息     for (int i = 0; i &lt; m2; ++i) {         int a, b;         cin &gt;&gt; a &gt;&gt; b;         international.emplace_back(a, b);     }     // 计算国内分配0~n个廊桥时的最大停靠数     vector&lt;int&gt; ca(n + 1);     for (int i = 0; i &lt;= n; ++i) {         ca[i] = countPlanes(domestic, i);     }     // 计算国际分配0~n个廊桥时的最大停靠数     vector&lt;int&gt; cb(n + 1);     for (int i = 0; i &lt;= n; ++i) {         cb[i] = countPlanes(international, i);     }     // 枚举所有分配方案,找到最大值     int maxAns = 0;     for (int i = 0; i &lt;= n; ++i) {         maxAns = max(maxAns, ca[i] + cb[n - i]);     }     cout &lt;&lt; maxAns &lt;&lt; endl;     return 0; }</pre><p><br/></p>
这道题暂未补解析。