题意大概是你要锯一系列的木板,如果下一个的长度和重量都比当前这个小,就不需要重置,反之需要重置1分钟,请你判断最少需要几分钟(初始需要1分钟)?
先按照重量或者长度进行排序,这样只需要看另一个因素里有多少递增子序列就可以了
例如第一个测试案例
4 9 5 2 2 1 3 5 1 4
按照长度排序后是
长度： 1 2 3 4 5
对应重量:4 1 5 9 2
重量序列中:4 5 9是一个递增序列 1 2是一个递增序列
共两个递增序列所以需要2分钟
执行时候先重置1分钟，选长度为5重量为2的，然后选长度为2重量为1的;再重置1分钟,第二次选长度为4,重量为9的,然后是长度为3,重量为5的,最后是长度为1,重量为4的
共2分钟
AC代码
/*
题很简单,但要考虑出现长度相同但重量不同的情况!!!(浪费我1个小时!!!)
*/
#include <stdio.h>
#define N 5001
typedef struct wooden
{int length;int weight; int visit;
}Wood;
Wood p[N];
void quick_Sort(Wood p[],int left,int right) //按照木棍长度对结构体进行排序,消除其中一个因素的影响
{int i = left , j = right;int pivot = p[(i+j)/2].length;Wood temp;while(i<=j){while (p[i].length<pivot){i++;}while (p[j].length>pivot){j--;}if(i<=j){if(p[i].length==p[j].length&&p[i].weight<p[j].weight){i++;j--;continue;}else{temp=p[i];p[i]=p[j];p[j]=temp;i++;j--; }}}if(i<right) quick_Sort(p,i,right);if(left<j) quick_Sort(p,left,j);
}
int find(int n) //此时长度已经是非递减序列,可从第n位看有几个重量递减序列或从1位开始看有几个递增序列
{int flag=0;int temp_weight;for(int i=1;i<=n;i++){if(p[i].visit==0){flag++; //flag为递增子序列的个数,如果全部是一个递增子序列,那么第一次循环所有的visit就都是1了temp_weight=p[i].weight;p[i].visit=1;for(int j=1;j<=n;j++){if(p[j].weight>=temp_weight&&p[j].visit==0) //找满足递增条件且未访问的节点{p[j].visit=1;temp_weight=p[j].weight; //更新缓存值,因为递增是和前一个比较不是和第一个比较continue;}}}}return flag;
}
void Init(int n)
{for(int i=1;i<=n;i++){p[i].visit=0;}
}
int main()
{int t,n;scanf("%d",&t);while (t--){scanf("%d",&n);for (int i = 1; i <= n; i++){scanf("%d %d",&p[i].length,&p[i].weight);}if(n==1){printf("1\n");continue;}else{Init(n); //因为有多个测试案例,因此每一个测试案例都有要先重置结构体里的visitquick_Sort(p,1,n);printf("%d\n",find(n));continue;} }return 0;
}
//poj 1065