DOC

DAYIN

By Ryan Bailey,2014-08-23 07:43
8 views 0
DAYIN

     1 1 Job schedule .............................................................................................................................. 1

    2 dp;set ...................................................................................................................................... 4 3 背包........................................................................................................................................... 6

    4 Maximal .................................................................................................................................... 8

1 Job schedule

    把任务按截止时间按截止时间从小到大进行处理.

    当出现冲突时,优先去掉前面的需求大的.

    #include <iostream>

    #include <algorithm>

    using namespace std;

    struct data{int w,d;};

    data a[800000];

    int n,t,b[800001],ch;

    int cmp(data i,data j)

    {

     return (i.d<j.d);

    }

    void change(int i,int j)

    {

     ch=b[i]; b[i]=b[j]; b[j]=ch; }

    void dui1(int i)

    {

     while (i>1)

     if (b[i]<=b[i/2]) return;

     else {change(i,i/2); i/=2;} }

    void dui2(int i)

    {

     while (i*2<t)

     if (b[i*2]<=b[i*2+1])

     if (b[i]<b[i*2+1]) {change(i,i*2+1); i=i*2+1;}

     else return;

     else

     if (b[i]<b[i*2]) {change(i,i*2); i*=2;}

     else return;

     if (i*2==t&&b[i]<b[t]) change(i,t); }

    void work()

     2

    {

     int i,l,tw;

     l=0; tw=0; t=0;

     for (i=0;i<n;i++)

     {

     while (t&&b[1]>a[i].w&&tw+a[i].w>a[i].d)

     {

     tw-=b[1]; l++;

     change(1,t); t--;

     dui2(1);

     }

     if (tw+a[i].w<=a[i].d)

     {

     tw+=a[i].w;

     t++; b[t]=a[i].w;

     dui1(t);

     }

     else l++;

     }

     printf("%d\n",n-l); }

    /*void prepare() {

     int i,j;

     j=0;

     for (i=1;i<n;i++)

     if (a[j].d<a[i].d)

     {

     j++; a[j]=a[i];

     }

     n=j+1;

    }*/

    int main()

    {

     int i;

     scanf("%d",&n);

     for (i=0;i<n;)

     {

     scanf("%d%d",&a[i].w,&a[i].d);

     if (a[i].d<a[i].w) n--;

     else i++;

     }

     sort(a,a+n,cmp);

     //prepare();

     3

     work();

     return 0;

    }

#include<iostream>

     #include<queue>

    #include<string>

    #include<vector>

    #include<algorithm>

    using namespace std;

struct ele

    {

     int q,d;

    };

ele order[800101];

    int n;

//注意结构体的排序

priority_queue<ele, vector<ele>, less<ele> > ipq;// greater<int>

    int cmp(const void* a,const void* b) {

     return ((ele*)a)->d-((ele*)b)->d; }

bool operator< (const ele& a, const ele& b)

    {

     return a.q < b.q;

    }

bool operator> (const ele& a, const ele& b)

    {

     return a.q > b.q;

    }

int main()

     4

    {

     scanf("%d",&n);

     int i;

     for(i=0;i<n;i++)

     scanf("%d%d",&order[i].q,&order[i].d);

     qsort(order,n,sizeof(ele),cmp);

     int num,dn;

     num=0;

     dn=0;

     for(i=0;i<n;i++)

     {

     if(order[i].q>order[i].d)

     continue;

     if(dn+order[i].q<=order[i].d)

     {

     num++;

     dn+=order[i].q;

     ipq.push(order[i]);

     }

     else

     {

     if(ipq.top().q>order[i].q)

     {

     dn-=ipq.top().q-order[i].q;

     ipq.pop();

     ipq.push(order[i]);

     }

     }

     }

     printf("%d\n",num);

     return 0;

    }

2 dp;set

    include <cstdio>

    #include <set>

    #include <cmath>

     5 using namespace std;

    int n, m, x[10000], y[10000], sum, limit; set < int > p[5001];

void solve_case() {

     scanf("%d", &m);

     sum = 0;

     for (int i = 0; i < n; i++) {

     scanf("%d %d", &x[i], &y[i]);

     sum += x[i];

     }

     if (sum == n / 2 * m) {

     printf("No solution\n");

     return;

     }

     limit = n / 2 * m;

     int ans;

     char ch;

     ans = -1;

     if (sum > n / 2 * m) {

     for (int i = 1; i <= n / 2; i++) p[i].clear();

     for (int j = 0; j < n; j++)

     for (int i = n / 2 - 1; i >= 0; i--) {

     for (set<int> :: iterator iter = p[i].begin();

    iter != p[i].end(); iter++)

     if ((*iter) + x[j] <=

    sum/*limit*/) p[i+1].insert((*iter) + x[j]);

     }

     for (set<int> :: iterator iter = p[n/2].begin(); iter !=

    p[n/2].end(); iter++)

     if (min((*iter), sum - (*iter)) > ans) {

     ans = min((*iter), sum - (*iter));

     ch = 'W';

     }

     }

     if (sum < n / 2 * m){

     sum = n * m - sum;

     for (int i = 1; i <= n / 2; i++) p[i].clear();

     for (int j = 0; j < n; j++)

     for (int i = n / 2 - 1; i >= 0; i--) {

     for (set<int> :: iterator iter = p[i].begin(); iter != p[i].end(); iter++)

     6

     if ((*iter) + y[j] <= sum /*limit*/) p[i+1].insert((*iter) + y[j]);

     }

     for (set<int> :: iterator iter = p[n/2].begin(); iter !=

    p[n/2].end(); iter++)

     if (min((*iter), sum - (*iter)) > ans) {

     ans = min((*iter), sum - (*iter));

     ch = 'B';

     }

     }

     if (ans == -1) printf("No solution\n");

     else {

     double tmp = ans * 100.0 / (n / 2 * m);

     if (fabs(tmp - 50.0) < 1e-7) {

     printf("No solution\n");

     return;

     }

     printf("%c %.2lf\n", ch, tmp);

     }

    }

int main()

    {

     p[0].clear();

     p[0].insert(0);

     while (scanf("%d", &n) != EOF)

     solve_case();

     //printf("No solution\n");

     return 0;

    }

3 背包

    #include <cstdio>

    #include <cstring>

    #include <algorithm>

const int Max = 100010;

struct NOD

    {

     7

     int A, C;

    };

    NOD nod[110];

int n, m;

     int dp[Max], num[Max], id[Max];

bool cmp(NOD p,NOD q)

    {

     if(p.A == q.A) return p.C <= q.C;

     return p.A < q.A;

    }

int main()

    {

     while(scanf("%d%d",&n,&m) != EOF&&n)

     {

     int i, j;

     for(i = 0;i < n;i ++) scanf("%d",&nod[i].A);

     for(i = 0;i < n;i ++) scanf("%d",&nod[i].C);

     std::sort(nod,nod+n,cmp);

     memset(dp,0,(m+1)*sizeof(int));

     memset(id,-1,(m+1)*sizeof(int));

     dp[0] = 1;

     int max = 0;

     for(i = 0;i < n;i ++)

     {

     max += nod[i].A*nod[i].C;

     if(max > m) max = m;

     for(j = nod[i].A;j <= max;j ++)

     {

     if(dp[j]) continue;

     int tmp = j - nod[i].A;

     if(!dp[tmp]) continue;

     if(id[tmp] == i)

     {

     if(num[tmp] >= nod[i].C) continue;

     num[j] = num[tmp] + 1;

     }

     else num[j] = 1;

     id[j] = i;

     dp[j] = 1;

     }

     8

     }

     int ans = 0;

     for(i = 1;i <= m;i ++)

     if(dp[i])

     ans ++;

     printf("%d\n",ans);

     }

    return 0;

    }

4 Maximal

     //pVals是商品的价格,target就是M

    // ASSUMES pVals is sorted in non-decreasing order // Outer loop

    // at the end of each step i, ret is the number of valid ways of getting a sum

    // between target - pVals[i] + 1 and target (inclusive) // (valid meaning that if pVals[j] <= (target - sum). pVals[j] isincluded in the

    sum

    // at step i if pVals[i] == last_value, we already have all possiblities

    // otherwise, we can include all values before i in the sum (cumSum)

    // and count how many ways there are to get sums between // target - pVals[i] + 1 and target - last_value // to do this we find out how many ways there are to get sum the values from

    // i to valCnt -1 to get a sum between

    // target - pVals[i] + 1 - cumSum and target - last_value - cumSum #include <stdio.h>

    #include <string.h>

    #include <algorithm>

    using namespace std;

    int number[40],n,m;

    __int64 dp[1001];

    __int64 Solve()

    {

     int i,j,curtag,curbot,cursum,lastval,curval,k;

     lastval=0;cursum=0;

     __int64 r=0;

     for(i=0;i<n&&cursum<m;i++)

     {

     curval=number[i];

     9

     if(curval>lastval)

     {

     curtag=m-cursum-lastval;

     curbot=m-cursum-curval+1;

     if(curbot<=0)

     {

     curbot=0;

     if(cursum==0)curbot=1;//避免空集

     }

     for(j=0;j<=curtag;j++)dp[j]=0;

     dp[0]=1;

     for(j=i;j<n;j++)

     for(k=curtag;k>=number[j];k--)

     dp[k]=dp[k]+dp[k-number[j]];

     for(j=curtag;j>=curbot;j--)

     r+=dp[j];

     }

     cursum+=curval;

     lastval=curval;

     }

     return r;

    }

    int main()

    {

     int t,i,k;

     scanf("%d",&t);

     for(k=1;k<=t;k++)

     {

     scanf("%d%d",&n,&m);

     memset(dp,0,sizeof(dp));

     for(i=0;i<n;i++)scanf("%d",&number[i]);

     sort(number,number+n);

     __int64 r=Solve();

     printf("%d %I64d\n",k,r);

     }

    }

Report this document

For any questions or suggestions please email
cust-service@docsford.com