zoj 1025 Wooden Sticks
テーマ:zoj 1025
木の棒を長さで並べ替えてから、対応する重量で構成される配列の非減算子配列の個数を計算します.
関連コード(悲しいことに、このコードはpoj1065とhdoj1051の下で通過できず、具体的に何が原因なのかを見るのがおっくうだ)
木の棒を長さで並べ替えてから、対応する重量で構成される配列の非減算子配列の個数を計算します.
関連コード(悲しいことに、このコードはpoj1065とhdoj1051の下で通過できず、具体的に何が原因なのかを見るのがおっくうだ)
/* zoj 1025 Wooden sticks */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 5010
struct stick{
int length;
int weight;
};
typedef struct stick stick;
int cmpStick(const void * a, const void * b);
int countSubsequence(int a[], int length);
int main(void)
{
int caseNum,n,i;
stick sticks[MAX];
int weights[MAX];
scanf("%d", &caseNum);
while(caseNum-- > 0)
{
scanf("%d", &n);
for(i = 0; i < n; i++)
{
scanf("%d %d", &sticks[i].length,&sticks[i].weight);
}
qsort(sticks,n,sizeof(stick),cmpStick);
for(i = 0; i < n; i++)
weights[i] = sticks[i].weight;
printf("%d
", countSubsequence(weights,n));
}
return 0;
}
int cmpStick(const void *a, const void *b)
{
stick x,y;
x = *(stick const *)a;
y = *(stick const *)b;
if(x.length > y.length)
return 1;
else
return 0;
}
int countSubsequence(int a[], int length)
{
int isVisited[MAX];
int i,count,prevIndex;
int resCount = 0;
memset(isVisited,0,sizeof(isVisited));
for(count =0; count < length; )
{
for(i = 0; i < length; i++)
if(!isVisited[i])
{
prevIndex = i;
isVisited[i] = 1;
count++;
break;
}
if(i == length)
break;
for(i = prevIndex+1; i < length; i++)
if(!isVisited[i])
{
if(a[prevIndex] <= a[i])
{
isVisited[i] = 1;
count++;
prevIndex = i;
}
}
resCount++;
}
return resCount;
}