当前位置：首页 > news >正文

HDU中的贪心算法

news 来源：原创 2024/9/20 8:05:51

//贪心算法的基本步骤
//1、从问题的某个初始解出发。
//2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，
// 得到一个部分解，缩小问题的范围或规模。
//3、将所有部分解综合起来，得到问题的最终解。

题目：http://acm.hdu.edu.cn/problemclass.php?id=29

//1050 Moving Tables
//1 如果没有交叉,则总时间为 1 * 10
//如果有交叉一层，则总时间为 2 * 10
//如果交叉n层，则总时间为（n + 1）* 10

#include <iostream> 
using namespace std; 
int main() 
{ 
int t,i,j,N,P[200];
int s,d,temp,k,min; 
cin>>t; 
for(i=0;i<t;i++) 
{ 
   for(j=0;j<200;j++) 
    P[j]=0; 
   cin>>N; 
   for(j=0;j<N;j++) 
   { 
    cin>>s>>d; 
    s=(s-1)/2; 
    d=(d-1)/2;          
    if(s>d) 
    { 
     temp=s; 
     s=d; 
     d=temp; 
    } 
    for(k=s;k<=d;k++) 
     P[k]++; 
   } 
   min=-1; 
   for(j=0;j<200;j++) 
    if(P[j]>min) 
     min=P[j]; 
   cout<<min*10<<endl; 
} 
return 0; 
}

/*
//1009 FatMouse' Trade
//经典的背包问题

#include <iostream>
#include <iomanip>
using namespace std;
struct date 
{
int f;
int j;
double r;
}d[1000];

int cmp (const void *a , const void *b)
{
return (*(date *)a).r > (*(date *)b).r ? 1 : -1;
}

int main()
{
int m , n , i ;
double sum;
while(cin>>m>>n, m+1 || n+1)
{
   for(i=0; i<n; i++)
   {
    cin>>d[i].j>>d[i].f;//j代表价值，f代表重量
    d[i].r = d[i].j * 1.0 / d[i].f;
   }
   qsort(d,n,sizeof(d[0]),cmp);
   sum = 0;
   for(i=n-1; i>=0; i--)
   {
    if(d[i].f <= m )
    {
     sum += d[i].j;
     m -= d[i].f;
    }
    else
     break;
   }
   if(m>0)
    sum += (double)m/d[i].f * d[i].j;
   cout<<fixed<<setprecision(3)<<sum<<endl;
}
return 0;
}