Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

真不知道是不是数据的问题!难道背包九一定是正确的?没人质疑出题人的思路么?附我的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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator