Wooden Sticks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8899 Accepted Submission(s): 3630
【解题思路】初学贪心仅知道一些理论的知识，这题说是贪心自己也没啥感觉，做题的思路是在抛开贪心的概念然后按照自己的想法实现出来，实现之后想在思路中找到贪心的影子，只能看到每次都是找尽可能多的stick仅此而已，Pursuiting...
Wa的原因是当时没考虑到stick的选择可以是不连续的，直接将排序后的次元素的比较上将后面一个跟前面一个进行比较。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define SIZE 5002 using namespace std; typedef struct sticks{
int L, w;
}sticks;
sticks stick[SIZE];
bool visit[SIZE];
int n; bool cmp(const sticks& a, const sticks& b)
{
if(a.w == b.w)
return a.L < b.L;
else return a.w < b.w;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int T, sum;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i=; i<n; ++i)
scanf("%d%d", &stick[i].L, &stick[i].w);
sort(stick, stick+n, cmp);
sum = ;
memset(visit, false, sizeof(visit));
int curmax = ;
for(int i=; i<n; ++i)
{
if(visit[i]) continue;
curmax = stick[i].L;
sum++;
for(int j=i+; j<n; ++j)
{
if(!visit[j] && stick[j].L >= curmax)
{
visit[j] = true;
curmax = stick[j].L;
}
}
}
/* for(int i=0; i<n; ++i)
if(!i || stick[i].L<stick[i-1].L) sum++;
*/
printf("%d\n", sum);
}
return ;
}