Hiking
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 76 Accepted Submission(s): 42
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.
4
8
4 1 3 2 2 1 0 3
5 3 6 4 2 1 7 6
8
3 3 2 0 5 0 3 6
4 5 2 7 7 6 7 6
8
2 2 3 3 3 0 0 2
7 4 3 6 3 2 2 5
8
5 6 5 3 3 1 2 4
6 7 7 6 5 4 3 5
/**
题意:现在有n个人,然后soda想要n个人尽可能多的去野营,每个人去野营是要在soda询问他时,
他所知道的去的人数大于等于L[i] 小于等于R[i] 然后问哪种询问顺序,可以使去的人数最多
做法:结构体 + 优先队列
首先第一个人的L[i]必须是0,然后在同样的下标为L[i]的进队列,
然后队列中的元素按照r[i]的大小排序,使得R[i]最小的优先
**/
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define maxn 100000 + 10
int vis[maxn];
int mmap[maxn];
struct Node
{
int l;
int r;
int id;
bool operator <(const Node &a)const
{
return r > a.r;
}
Node()
{
l = ;
r = ;
id = ;
}
} node[maxn];
int cmp(Node a,Node b)
{
if(a.l != b.l) return a.l < b.l;
return a.r , b.r;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=; i<n; i++)
{
scanf("%d",&node[i].l);
}
for(int i=; i<n; i++)
{
scanf("%d",&node[i].r);
node[i].id = i+;
}
sort(node,node+n,cmp);
memset(mmap,,sizeof(mmap));
priority_queue<Node>que;
while(!que.empty()) que.pop();
int sum = ;
int tt = ;
int tt1 = n-;
if(node[].l != )
{
printf("0\n");
for(int i=; i<n; i++)
{
printf("%d",i+);
if(i!= n-) printf(" ");
else printf("\n");
}
continue;
}
que.push(node[]);
Node now,tmp;
int i = ;
while(!que.empty())
{
for(; node[i].l == sum&&i<n; i++)
que.push(node[i]);
while(!que.empty())
{
if(que.top().r >= sum)
{
int tx = que.top().id;
mmap[tt++] = tx;
sum++;
que.pop();
break;
}
else
mmap[tt1--] = que.top().id;
que.pop();
}
for(;node[i].l == sum&&i<n;i++)
que.push(node[i]);
}
for(;i<n;i++)
mmap[tt1--] = node[i].id;
printf("%d\n",tt);
for(i=;i<n;i++)
{
printf("%d",mmap[i]);
if(i!= n-) printf(" ");
else printf("\n");
}
}
return ;
}