题目大意:要加工n双筷子,筷子的长度和重量事先已经知道。加工有一个设置时间,而加工的规则如下:
1.第一双筷子的设置时间为1分钟;
2.后面的筷子如果长度和重量都大于前面的筷子,则不需要设置,可直接加工,否则需1分钟设置时间。
求出加工所给的筷子的一个序列,使总的设置时间最短。
输入:
第一行:测试的组数
后面每组测试数据的第一行:筷子的数目n(1<=n<=5000)
后面每组测试数据的第二行:n双筷子的长度和重量。
输出:每组测试数据的最短时间。
解题思路:
1.贪心,变种的会场安排。
2.首先将筷子按长度从小到大排列,然后根据重量进行贪心。每次找到满足重量大于当前筷子的就将其加入到这个筷子的序列中,然后更新这组筷子的重量为新加入的筷子的重量,然后继续贪心。最后的序列的组数即为最短的时间。
核心代码:
 

int greedySelector()  
{  
    int i,j,count;  
    count=1;  
    for(i=1;i<=k;i++)  
        if(a[i]==false){  
            j=i;  
            a[i]=true;  
            break;  
        }  
    for(i=1;i<=k;i++)  
    {  
        if(a[i]==false){  
            if(ac[i].f>=ac[j].f)  
            {  
                a[i]=true;  
                j=i;  
                count++;  
            }  
            else
                a[i]=false;  
        }  
    }  
    return count;  
}  


 

发表评论

电子邮件地址不会被公开。

Post Navigation