Вино

This message was edited 1 time. Last update was at 27/03/2012 10:26:40

Може некој да даде идеа за задачата?

Креативен almost-but-not-quite брутфорс со бинарно пребарување. Се делат вината во две групи и пробуваш секоја комбинација на вина од едната група да ја спариш со најдобрата комбинација од другата група.

This message was edited 1 time. Last update was at 04/01/2013 15:07:11

Може малку да подобјасниш, не ми е јасен делот "спаруваме со најдобрата комбинација од вториот дел". Ако пробуваме секоја комбинација од првиот со секоја од вториот, пак имаме 2^32 комбинации...

amijoski wrote:Може малку да подобјасниш, не ми е јасен делот "спаруваме со најдобрата комбинација од вториот дел". Ако пробуваме секоја комбинација од првиот со секоја од вториот, пак имаме 2^32 комбинации...

а делот "... со бинарно пребарување" од текстот на obi1kenobi?

Може да ми се даде пример како ќе оди тој брут форс?

Јас искуцав нешто различно ама ми паѓа на време на 4 примери...

#include<cctype>
#include<cmath>
#include<string>
#include<list>
#include<deque>
#include<stack>
#include<utility>
#include<sstream>
#include<bitset>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<set>
#include<iostream>
#include<climits>
#define mp make_pair
#define pb push_back
#define ms(x,y) memset((x),(y),sizeof((x)))
#define all(c) c.begin(),c.end()
using namespace std;
struct pari
{
    long long cn,vk;
};
bool cmp(const pari &a, const pari &b)
{
    if(a.cn<b.cn)
        return true;
    else if(a.cn==b.cn && a.vk<b.vk)
        return true;
    else return false;
}
int main()
{
    long long n,h,k;
    cin>>n>>h>>k;
    long long should=30000000*30,current=0,cnt=0;
    int i,j,l=0;
    vector<int> ima,cen,pro;
    for(i=0;i<h;i++)
    {
        cin>>j;
        ima.pb(j-1);
    }
    for(i=0;i<n;i++)
    {
        cin>>j;
        cen.pb(j);
        if(l<ima.size())
            if(i==ima[l])
            {
                current+=j;
                l++;
            }
    }
    for(i=0;i<n;i++)
    {
        cin>>j;
        pro.pb(j);
        cnt+=j;
    }
    if(cnt<k)
    {
        cout<<"-1"<<endl;
        return 0;
    }
    vector<pari> a;
    pari tmp;
    tmp.vk=0;
    tmp.cn=0;
    a.pb(tmp);
    for(i=0;i<n;i++)
    {
        l=a.size();
        sort(all(a),cmp);
        for(j=0;j<l;j++)
        {
            while(j+1<l && a[j].cn==a[j+1].cn)
                j++;
            tmp=a[j];
            tmp.cn+=cen[i];
            tmp.vk+=pro[i];
            if(tmp.vk>=k)
                should=min(should,tmp.cn);
            else
                a.pb(tmp);
        }
    }
    cout<<should-current<<endl;
    return 0;
}

Прочитај за divide and conquer. И после тоа прочитај го ова

http://apps.topcoder.com/forums/?module=Thread&threadID=622665&start=0&mc=12#1017888

Имаш и едиториал за истата задача ако ова не помогне.

Кико ти во favorites си ја чуваш задачава?

This message was edited 1 time. Last update was at 01/03/2013 04:23:06

Google skills