Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

真不知道是不是数据的问题！难道背包九一定是正确的？没人质疑出题人的思路么？附我的WA贪心代码

Posted by Fsss at 2015-07-16 16:28:07 on Problem 1787
In Reply To:像这样贪心过不了的，我试过了 Posted by:tmpbt at 2004-09-09 10:19:28

#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 7500
#define MOD 1000000007
#define EPS 0.00000001
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    int c1,c2,c3,c4,p;
    while (scanf("%d%d%d%d%d", &p, &c1, &c2, &c3, &c4)&&(p||c1||c2||c3||c4)) {
        while (c1+5*c2+10*c3+25*c4>p) {
            if (c4&&c1+5*c2+10*c3+25*(c4-1)>=p) {
                c4--;continue ;
            }
            if (c3&&c1+5*c2+10*(c3-1)+25*c4>=p) {
                c3--;continue ;
            }
            if (c2&&c1+5*(c2-1)+10*c3+25*c4>=p) {
                c2--;continue ;
            }
            if (c1&&(c1-1)+5*c2+10*c3+25*c4>=p) {
                c1--;continue ;
            }
            break ;
        }
        if (c1+5*c2+10*c3+25*c4==p) printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", c1, c2, c3, c4);
        else printf("Charlie cannot buy coffee.\n");
    }
    return 0;
}

Followed by:

。。。。。贪心是不可取的。试试下面这组数据吧 (54) Fsss 2015-07-16 17:08:28
- Re:。。。。。贪心是不可取的。试试下面这组数据吧 (64) 5120172804 2019-04-10 18:07:32
- Re:。。。。。贪心是不可取的。试试下面这组数据吧 (17) 5120172804 2019-04-10 18:07:58

Post your reply here:

User ID:
Password:
Title:

Content:

> #include<cmath>
> #include<queue>
> #include<cstdio>
> #include<vector>
> #include<cstring>
> #include<iostream>
> #include<algorithm>
> #define N 7500
> #define MOD 1000000007
> #define EPS 0.00000001
> #pragma comment(linker, "/STACK:102400000,102400000")
> using namespace std;
> typedef long long LL;
> int read()
> {
>     int x=0,f=1;char ch=getchar();
>     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
>     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
>     return x*f;
> }
> int main()
> {
>     int c1,c2,c3,c4,p;
>     while (scanf("%d%d%d%d%d", &p, &c1, &c2, &c3, &c4)&&(p||c1||c2||c3||c4)) {
>         while (c1+5*c2+10*c3+25*c4>p) {
>             if (c4&&c1+5*c2+10*c3+25*(c4-1)>=p) {
>                 c4--;continue ;
>             }
>             if (c3&&c1+5*c2+10*(c3-1)+25*c4>=p) {
>                 c3--;continue ;
>             }
>             if (c2&&c1+5*(c2-1)+10*c3+25*c4>=p) {
>                 c2--;continue ;
>             }
>             if (c1&&(c1-1)+5*c2+10*c3+25*c4>=p) {
>                 c1--;continue ;
>             }
>             break ;
>         }
>         if (c1+5*c2+10*c3+25*c4==p) printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", c1, c2, c3, c4);
>         else printf("Charlie cannot buy coffee.\n");
>     }
>     return 0;
> }
>

Home Page Go Back To top