NC25252. 集结
描述
输入描述
第一行两个整数n,m（1<=m<=n<=100,000）表示格子的个数是n，一共有m位上古大神
接下来m行，有2个整数ai，bi (1<=ai<=n, 1<=bi<=1,000,000)，表示第i位上古大神在坐标ai的位置上，有bi的体力。保证上古大神初始不会在同一共位置上
接下来一行，包括n个整数c1,c2......cn，第i个整数ci(-1,000,000<=ci<=1,000,000)表示坐标为i的位置的情况：
等于0:这个位置有一位上古大神；
不等于0:这个位置有一个事件。
输出描述
第一行输出一个数代表集结点。
第二行输出m个数，第i个数代表第i个移动的上古大神序号。这个序号和输入的顺序相同。
如果有多种方案，输出任意一种。如果不能使所有人都到达，那么输出-1。
示例1
输入:
8 3 1 15 8 1 5 10 0 -5 -5 -5 0 -5 -5 0
输出:
7 3 1 2
说明:
一个1*8的格子，初始在1、5、8的地方都有一个上古大神，体力是15、10、1。选择7作为集结点。C++11(clang++ 3.9) 解法, 执行用时: 37ms, 内存消耗: 4760K, 提交时间: 2019-04-24 10:49:30
#include <bits/stdc++.h>
#define MAX_N 100005
#define DEBUG 0
#define a first
#define b second
using namespace std;
typedef pair<int, long long> P;
int n, m;
P master[MAX_N];
int c[MAX_N];
P mp[MAX_N];
int id[MAX_N];
int vis[MAX_N];
stack<P> l;
stack<P> r;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1 ; i <= m; i++) {
cin >> master[i].a >> master[i].b;
mp[master[i].a] = master[i];
id[master[i].a] = i;
}
for (int i = 1; i <= n; i++) cin >> c[i];
sort(master + 1, master + m + 1);
P curr = master[1];
int max_l = master[1].a;
l.push(curr);
for (int i = master[1].a; i <= n; i++) {
curr.b += c[i];
if (curr.b < 0) break;
max_l = max(max_l, i);
if (!c[i]) {
P p = mp[i];
if (p.b > curr.b) {
curr = p;
l.push(curr);
}
}
}
curr = master[m];
int max_r = master[m].a;
r.push(curr);
for (int i = master[m].a; i >= 1; i--) {
curr.b += c[i];
if (curr.b < 0) break;
max_r = min(max_r, i);
if (!c[i]) {
P p = mp[i];
if (p.b > curr.b) {
curr = p;
r.push(curr);
}
}
}
#if DEBUG
cout << "max_l: " << max_l << endl;
cout << "max_r: " << max_r << endl;
#endif
if (max_l + 1 < max_r) {
cout << -1 << endl;
}
else {
int target = max_l;
memset(vis, 0, sizeof vis);
cout << target << endl;
while (!l.empty()) {
P p = l.top();
l.pop();
if (vis[id[p.a]]) continue;
cout << id[p.a] << ' ';
vis[id[p.a]] = 1;
}
while (!r.empty()) {
P p = r.top();
r.pop();
if (vis[id[p.a]]) continue;
cout << id[p.a] << ' ';
vis[id[p.a]] = 1;
}
for (int i = 1; i <= m; i++) {
if (vis[i]) continue;
cout << i << ' ';
}
cout << endl;
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 40ms, 内存消耗: 4884K, 提交时间: 2019-04-25 12:07:50
#include <bits/stdc++.h>
#define MAX_N 100005
#define DEBUG 0
#define a first
#define b second
using namespace std;
typedef pair<int, long long> P;
int n, m;
P master[MAX_N];
int c[MAX_N];
P mp[MAX_N];
int id[MAX_N];
int vis[MAX_N];
stack<P> l;
stack<P> r;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1 ; i <= m; i++) {
cin >> master[i].a >> master[i].b;
mp[master[i].a] = master[i];
id[master[i].a] = i;
}
for (int i = 1; i <= n; i++) cin >> c[i];
sort(master + 1, master + m + 1);
P curr = master[1];
int max_l = master[1].a;
l.push(curr);
for (int i = master[1].a; i <= n; i++) {
curr.b += c[i];
if (curr.b < 0) break;
max_l = max(max_l, i);
if (!c[i]) {
P p = mp[i];
if (p.b > curr.b) {
curr = p;
l.push(curr);
}
}
}
curr = master[m];
int max_r = master[m].a;
r.push(curr);
for (int i = master[m].a; i >= 1; i--) {
curr.b += c[i];
if (curr.b < 0) break;
max_r = min(max_r, i);
if (!c[i]) {
P p = mp[i];
if (p.b > curr.b) {
curr = p;
r.push(curr);
}
}
}
#if DEBUG
cout << "max_l: " << max_l << endl;
cout << "max_r: " << max_r << endl;
#endif
if (max_l + 1 < max_r) {
cout << -1 << endl;
}
else {
int target = max_l;
memset(vis, 0, sizeof vis);
cout << target << endl;
while (!l.empty()) {
P p = l.top();
l.pop();
if (vis[id[p.a]]) continue;
cout << id[p.a] << ' ';
vis[id[p.a]] = 1;
}
while (!r.empty()) {
P p = r.top();
r.pop();
if (vis[id[p.a]]) continue;
cout << id[p.a] << ' ';
vis[id[p.a]] = 1;
}
for (int i = 1; i <= m; i++) {
if (vis[i]) continue;
cout << i << ' ';
}
cout << endl;
}
return 0;
}