Constructing Roads In JGShining's Kingdom
JGShining's kingdom consists of 2n(n is no more than 500,000) small cities which are located in two parallel lines.
Half of these cities are rich in resource (we call them rich cities) while the others are short of resource (we call them poor cities). Each poor city is short of exactly one kind of resource and also each rich city is rich in exactly one kind of resource. You may assume no two poor cities are short of one same kind of resource and no two rich cities are rich in one same kind of resource.
With the development of industry, poor cities wanna import resource from rich ones. The roads existed are so small that they're unable to ensure the heavy trucks, so new roads should be built. The poor cities strongly BS each other, so are the rich ones. Poor cities don't wanna build a road with other poor ones, and rich ones also can't abide sharing an end of road with other rich ones. Because of economic benefit, any rich city will be willing to export resource to any poor one.
Rich citis marked from 1 to n are located in Line I and poor ones marked from 1 to n are located in Line II.
The location of Rich City 1 is on the left of all other cities, Rich City 2 is on the left of all other cities excluding Rich City 1, Rich City 3 is on the right of Rich City 1 and Rich City 2 but on the left of all other cities ... And so as the poor ones.
But as you know, two crossed roads may cause a lot of traffic accident so JGShining has established a law to forbid constructing crossed roads.
For example, the roads in Figure I are forbidden.
In order to build as many roads as possible, the young and handsome king of the kingdom - JGShining needs your help, please help him. ^_^
Input
Each test case will begin with a line containing an integer n(1 ≤ n ≤ 500,000). Then n lines follow. Each line contains two integers p and r which represents that Poor City p needs to import resources from Rich City r. Process to the end of file.
Output
For each test case, output the result in the form of sample.
You should tell JGShining what's the maximal number of road(s) can be built.
Sample Input
2
1 2
2 1
3
1 2
2 3
3 1 Sample Output
Case 1:
My king, at most 1 road can be built.
Case 2:
My king, at most 2 roads can be built.
Hint
Huge input, scanf is recommended.
测试样例分析：
#include<stdio.h>
#include<stdlib.h>
#define MAX 500001
using namespace std;
int put(int arr[], int l, int r, int key){
//在arr[]中用二分法查找插入位置
int mid;
if(arr[r]<=key)
return r + 1;
while (l < r){
mid = l + (r - l) / 2;
if (arr[mid] <= key)
l = mid + 1;
else
r = mid;
}
return l;
}
int LIS(int A[], int n){//传入数组A,与数组长度n
int i = 0, len = 1 ,next;
int* B = (int *)malloc(sizeof(int) * (n + 1));//动态创建一个数组B
B[1] = A[0]; //第一个数不存在比较，所以直接放入
for (i = 1;i < n;i++){
int next = put(B, 1, len, A[i]);//next用来存放A[i]的插入位置
B[next] = A[i];
if(len<next) //len用来记录最长上升序列
len = next;
}
return len;
}
int main(){
int a[MAX]; //a数组用于存放rich和poor的对应关系(键值对应)
int n,num_Case=1;
while(scanf("%d",&n)!=EOF){
//输入
int v,u;
for(int i = 0;i<n;i++){
scanf("%d%d",&v,&u);
a[v-1] = u;
}
//算法核心
int k = LIS(a,n);
//输出 (注意：当road＞1 road要复数形式)
if(k == 1) printf("Case %d:\nMy king, at most 1 road can be built.\n\n", num_Case++);
else printf("Case %d:\nMy king, at most %d roads can be built.\n\n", num_Case++, k);
}
return 0;
} 补充最长上升序列： （此部分的部分内容是转载名为Alinshans的博客）
学习动态规划问题（DP问题）中，其中有一个知识点叫最长上升子序列（longest increasing subsequence），也可以叫最长非降序子序列，简称LIS。简单说一下自己的心得。
我们都知道，动态规划的一个特点就是当前解可以由上一个阶段的解推出， 由此，把我们要求的问题简化成一个更小的子问题。子问题具有相同的求解方式，只不过是规模小了而已。最长上升子序列就符合这一特性。我们要求n个数的最长上升子序列，可以求前n-1个数的最长上升子序列，再跟第n个数进行判断。求前n-1个数的最长上升子序列，可以通过求前n-2个数的最长上升子序列……直到求前1个数的最长上升子序列，此时LIS当然为1。
让我们举个例子：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度。
前1个数 d(1)=1 子序列为2；
前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7
前3个数 在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1
前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5
前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6
前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4
前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3
前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8
前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9
d(i)=max{d(1),d(2),……,d(i)} 我们可以看出这9个数的LIS为d(9)=5
总结一下，d(i)就是找以A[i]结尾的，在A[i]之前的最长上升子序列+1，当A[i]之前没有比A[i]更小的数时，d(i)=1。所有的d(i)里面最大的那个就是最长上升子序列。
int LIS(int A[],int n)
{
int* d = new int[n];
int len = 1;
int i,j;
for(i=0;i<n;i++)
{
d[i]=1;
for(j=0;j<i;j++)
{
if(A[j]<=A[i] && (d[j]+1)>=d[i])
d[i]=d[j]+1;
}
if(d[i]>len) len=d[i];
}
delete []d;
return len;
} 这个算法的时间复杂度为〇(n²)，并不是最优的算法。在限制条件苛刻的情况下，这种方法行不通。那么怎么办呢！有没有时间复杂度更小的算法呢？说到这里了，当然是有的啦！还有一种时间复杂度为〇(nlogn)的算法，下面就来看看。
我们再举一个例子：有以下序列A[]=3 1 2 6 4 5 10 7，求LIS长度。
我们定义一个B[i]来储存可能的排序序列，len为LIS长度。我们依次把A[i]有序地放进B[i]里。（为了方便，i的范围就从1~n表示第i个数）
A[1]=3，把3放进B[1]，此时B[1]=3，此时len=1，最小末尾是3
A[2]=1，因为1比3小，所以可以把B[1]中的3替换为1，此时B[1]=1，此时len=1，最小末尾是1
A[3]=2，2大于1，就把2放进B[2]=2，此时B[]={1,2}，len=2
同理，A[4]=6，把6放进B[3]=6，B[]={1,2,6}，len=3
A[5]=4，4在2和6之间，比6小，可以把B[3]替换为4，B[]={1,2,4}，len=3
A[6]=5，B[4]=5，B[]={1,2,4,5}，len=4
A[7]=10，B[5]=10，B[]={1,2,4,5,10}，len=5
A[8]=7，7在5和10之间，比10小，可以把B[5]替换为7，B[]={1,2,4,5,7}，len=5
最终我们得出LIS长度为5。但是，但是！！这里的1 2 4 5 7很明显并不是正确的最长上升子序列。是的，B序列并不表示最长上升子序列，它只表示相应最长子序列长度的排好序的最小序列。这有什么用呢？我们最后一步7替换10并没有增加最长子序列的长度，而这一步的意义，在于记录最小序列，代表了一种“最可能性”。假如后面还有两个数据8和9，那么B[6]将更新为8，B[7]将更新为9，len就变为7。读者可以自行体会它的作用。
因为在B中插入的数据是有序的，不需要移动，只需要替换，所以可以用二分查找插入的位置，那么插入n个数的时间复杂度为〇(logn)，这样我们会把这个求LIS长度的算法复杂度降为了〇(nlogn)。
int put(int arr[], int l, int r, int key){
//在arr[]中用二分法查找插入位置
int mid;
if(arr[r]<=key)
return r + 1;
while (l < r){
mid = l + (r - l) / 2;
if (arr[mid] <= key)
l = mid + 1;
else
r = mid;
}
return l;
}
int LIS(int A[], int n){//传入数组A,与数组长度n
int i = 0, len = 1 ,next;
int* B = (int *)malloc(sizeof(int) * (n + 1));//动态创建一个数组B
B[1] = A[0]; //第一个数不存在比较，所以直接放入
for (i = 1;i < n;i++){
int next = put(B, 1, len, A[i]);//next用来存放A[i]的插入位置
B[next] = A[i];
if(len<next) //len用来记录最长上升序列
len = next;
}
return len;
}
京公网安备 11010502036488号