转载请注明出处: http://www.cnblogs.com/fraud/ ——by fraud
Hiking
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 724 Accepted Submission(s): 384
Special Judge
1. he selects a soda not invited before;
2. he tells soda the number of soda who agree to go hiking by now;
3. soda will agree or disagree according to the number he hears.
Note: beta will always tell the truth and soda will agree if and only if the number he hears is no less than li and no larger than ri, otherwise he will disagree. Once soda agrees to go hiking he will not regret even if the final total number fails to meet some soda's will.
Help beta design an invitation order that the number of soda who agree to go hiking is maximum.
The first contains an integer n (1≤n≤105), the number of soda. The second line constains n integers l1,l2,…,ln. The third line constains n integers r1,r2,…,rn. (0≤li≤ri≤n)
It is guaranteed that the total number of soda in the input doesn't exceed 1000000. The number of test cases in the input doesn't exceed 600.
水题,先按li排序,然后不断地塞进优先队列
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author xyiyy @https://github.com/xyiyy
*/ #include <iostream>
#include <fstream> //#####################
//Author:fraud
//Blog: http://www.cnblogs.com/fraud/
//#####################
//#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <sstream>
#include <ios>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <cctype> using namespace std;
#define mp(X, Y) make_pair(X,Y)
#define pb(X) push_back(X)
#define rep(X, N) for(int X=0;X<N;X++)
#define rep2(X, L, R) for(int X=L;X<=R;X++)
typedef pair<int, int> PII; typedef pair<PII, int> PIII;
priority_queue<PIII, vector<PIII>, greater<PIII> > q;
int f[];
int l[];
int r[];
vector<int> v[]; class hdu5360 {
public:
void solve(std::istream &in, std::ostream &out) {
int n;
in >> n;
for (int i = ; i <= n; i++)in >> l[i];
for (int i = ; i <= n; i++) {
in >> r[i];
if (l[i])v[l[i]].pb(i);
else q.push(mp(mp(r[i], l[i]), i));
}
int num = n;
int ans = ;
int sz = ;
while (n) {
if (q.empty()) {
rep2(i, ans + , n) {
rep(j, v[i].size()) {
f[sz++] = v[i][j];
}
v[i].clear();
}
break;
}
PIII p = q.top();
q.pop();
int y = p.first.first;
int x = p.first.second;
int z = p.second;
f[sz++] = z;
if (x <= ans && y >= ans) {
ans++;
rep(i, v[ans].size()) {
int j = v[ans][i];
q.push(mp(mp(r[j], l[j]), j));
}
v[ans].clear();
}
}
out << ans << endl;
rep(i, sz) {
if (i)out << " ";
out << f[i];
}
out << endl;
}
}; int main() {
std::ios::sync_with_stdio(false);
std::cin.tie();
hdu5360 solver;
std::istream &in(std::cin);
std::ostream &out(std::cout);
int n;
in >> n;
for (int i = ; i < n; ++i) {
solver.solve(in, out);
} return ;
}