/*先按min从大到小排序，尽可能的先装满min，再把remain依次分配给各个瓶子，直到装满，
如果所有的都装满，还有剩余的就输出remain，但是如果还有没装满的就表示没有剩余了*/ 

#include<iostream>
using namespace std;

 typedef struct node{
    float min;
    float max;
    int n;
}NODE;
NODE sizes1[101];

       
int main()
{
    long amount;
    int num;
    float minimal,maximal;
    char c;
    while(cin>>c)
    {
        cin.putback(c);
        cin>>amount>>num;
        if(amout==0){cout<<0<<end;continue;}
        for(int i=1;i<=num;i++)
{cin>>minimal>>maximal;sizes1[i].min=minimal/1000;sizes1[i].max=maximal/1000;sizes1[i].n=0;}
      
        //按min的大小从大到小排列
        for(i=1;i<num;i++)
        {
             minimal=sizes1[i].min;
             int j=i;
            for(int k=i+1;k<=num;k++)
            {
                if(sizes1[k].min>minimal){minimal=sizes1[k].min;j=k;}
            }
            NODE t;
            t=sizes1[i];
            sizes1[i]=sizes1[j];sizes1[j]=t;
        }
        float remain=0,contain=0;
        for(i=1;i<=num;i++)
        {
            while(1)
            { 
                contain+=sizes1[i].min;
                remain=amount-contain;
                sizes1[i].n++;
                if(remain>=sizes1[i].min)continue;
                else 
                {
                    if(remain<0){contain-=sizes1[i].min;remain+=sizes1[i].min;sizes1[i].n--;}
                    break;
                }    
            }
        }
        for(i=1;i<=num;i++)
        {
            while(sizes1[i].n>0)
            {
                remain=remain-(sizes1[i].max-sizes1[i].min);
                if(remain>0)sizes1[i].n--;
                else        break;
            }
            if(remain<=0){remain=0;break;}
        }
        remain=remain*1000;
        cout<<remain<<endl;
    }                
    return 0;
}    
           

• Re:有同学帮我看看哪儿不对吗？example都通过了，就是wrong answer (2018) DavidWang 2005-09-13 22:09:00
  • Re:有同学帮我看看哪儿不对吗？example都通过了，就是wrong answer (29) DavidWang 2005-09-13 22:11:05
• Re:有同学帮我看看哪儿不对吗？example都通过了，就是wrong answer (2018) DavidWang 2005-09-13 22:09:48
  • 贪心不可以的 (0) zzningxp 2005-09-13 22:31:08
    • Re:贪心不可以的 (9) DavidWang 2005-09-13 23:19:17
      • 深搜可以过，15ms (13) tengshengbo 2005-09-13 23:23:02
        • 这个题好像容器很大时 肯定可以一点都不剩 (0) zzningxp 2005-09-13 23:36:16
          • “好像”是什么意思？容器容量不会太大的。 (0) tengshengbo 2005-09-13 23:40:38
            • the amount of wine to be bottled (in litres, between 0 and 1,000,000) 说错了不是容器是酒的总量 (0) zzningxp 2005-09-13 23:43:04
              • 有道理。可以证明的。 (0) tengshengbo 2005-09-13 23:45:08
                • 每个瓶子里放多少酒都有1%~5%的量可以变化 瓶子容量的范围也可以确定 这样就可以覆盖某个上界值以上所有的酒的总量 (0) zzningxp 2005-09-13 23:48:19
          • 这样可以减掉很大一部分搜索 然后再DP (0) zzningxp 2005-09-13 23:45:33
          • 在你的提醒下，我的搜索优化到了0ms (0) tengshengbo 2005-09-13 23:50:38
            • 你取的多大的上界? (0) zzningxp 2005-09-13 23:51:52
              • 450000。 (0) tengshengbo 2005-09-13 23:55:52
                • 这道题的上限怎么证明呢？ (0) Acsaga 2008-10-01 13:17:20
        • 你是怎么深搜的? 我还是只能DP, code look look (0) zzningxp 2005-09-13 23:54:36
          • dp才是正道。我是歪门邪道。哈哈。 (0) tengshengbo 2005-09-13 23:56:40
            • 4500/1% ?? 刚刚好? (0) zzningxp 2005-09-14 00:01:23