1940: 心急的C小加

迈不过友情╰ 2024-02-18 22:04 35阅读 0赞

### **1940: 心急的C小加** ###

时间限制: 1 Sec 内存限制: 64 MB  
提交: 168 解决: 71  
您该题的状态：**已完成**  
\[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]

### **题目描述** ###

C小加有一些木棒，它们的长度和质量都已经知道，需要一个机器处理这些木棒，机器开启的时候需要耗费一个单位的时间，如果第i+1个木棒的重量和长度都大于等于第i个处理的木棒，那么将不会耗费时间，否则需要消耗一个单位的时间。因为急着去约会，C小加想在最短的时间内把木棒处理完，你能告诉他应该怎样做吗？

### **输入** ###

第一行是一个整数T(1<T<1500)，表示输入数据一共有T组。 
每组测试数据的第一行是一个整数N（1<=N<=5000）,表示有N个木棒。接下来的一行分别输入N个木棒的L，W（0 < L ,W <= 10000），用一个空格隔开，分别表示木棒的长度和质量。

### **输出** ###

处理这些木棒的最短时间。

### **样例输入** ###

3 
 5 
 4 9 5 2 2 1 3 5 1 4 
 3 
 2 2 1 1 2 2 
 3 
 1 3 2 2 3 1

### **样例输出** ###

2
 1
 3

### **提示** ###

要点：先对长度排序，若相等则对重量排序（均为从小到大）

从小的重量开始，后面重量比他大的均标记为零（因为长度保证是从小到大排的），经过筛选，筛选数即为所求。

\#include<iostream> 
\#include<cstdio> 
\#include<algorithm> 
using namespace std; 
struct k 
\{ 
double l,w; 
\}a\[10010\]; 
double cmp(struct k x,struct k y) 
\{ 
if(x.l==y.l) 
return x.w<y.w; 
else 
return x.l<y.l; 
\} 
int main() 
\{ 
int n,m,i,j; 
cin>>n; 
while(n--) 
\{ 
double flag=0; 
int sum=0; 
cin>>m; 
for(i=0;i<m;i++) 
cin>>a\[i\].l>>a\[i\].w; 
sort(a,a+m,cmp); 
//for(i=0;i<m;i++) 
//cout<<a\[i\].l<<" "<<a\[i\].w<<endl; 
for(i=0;i<m;i++) 
\{ 
if(a\[i\].w) 
\{ 
flag=a\[i\].w; 
for(j=i+1;j<m;j++) 
\{ 
if(a\[j\].w>=flag) 
\{ 
flag=a\[j\].w; 
a\[j\].w=0; 
\} 
 
\} 
sum++; 
\} 
\} 
cout<<sum<<endl; 
\} 
return 0; 
\}

[Link 1]: http://xyoj.xynu.edu.cn/submitpage.php?id=1940
[Link 2]: http://xyoj.xynu.edu.cn/problemstatus.php?id=1940
[Link 3]: http://xyoj.xynu.edu.cn/bbs.php?pid=1940