[01分数规划][二分][精度][坑] POJ2976 Dropping tests

二分答案倒是容易想到,实现的话需要排序后贪心,但是坑在精度上

我用了printf(“%.0f\n”,ans); WA cout<<(int )(ans+0.5)<<endl; AC 就很玄学。。。。学到了学到了

 


//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define eps (1e-6)
using namespace std;
typedef long long LL;
const int maxn=1e3+5;
const int MOD=1e9+7;
const int INF=0x4f4f4f4f;

void read(int &x)
{
    char ch = getchar();
    x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
}

int a[maxn],b[maxn];
int n,k;
double tmp[maxn];
int check(double d)
{
    for (int i=1;i<=n;i++)
        tmp[i]=100.0*a[i]-d*b[i];
    sort(tmp+1,tmp+1+n);
    double sum=0.0;
    for (int i=n;i>k;i--)
        sum=sum+tmp[i];
    if(sum>eps)//try 0?
        return 1;
    else
        return 0;
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    while(~scanf("%d%d",&n,&k)&&n)
    {
        for (int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for (int i=1;i<=n;i++)
            scanf("%d",&b[i]);

        double l=0.0,r=100.0,mid;
        while(r-l>0.0001)
        {
            mid=(l+r)/2;
            if(check(mid))
                l=mid;
            else
                r=mid-0.0001;
        }
        cout<<(int)(r+0.5)<
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据