DOC

DAYIN

By Ryan Bailey,2014-08-23 07:43
9 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;