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