首页 » 贪心 » 正文

Yangyang loves AC

Yangyang loves AC

来源:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2193

Description

Yangyang takes part in the ACM Summer Training. She loves AC, but there is so much knowledge to learn, For example, Dynamic Programming, Greedy, Search, Graph, Data Structure, and so on. So she decides to ask some other ACMers for help. There are some details below:

There are M (1 <= M <= 20000) ACMers. As we know, ACMers are always busy, so she decides to ask each ACMer at most once.

After being helped, Yangyang will fell happy, The i-th ACMer will bring her Hi(1 <= Hi <= 2^13)Happiness. Moreover, Yangyang prefer to numbers that are power of 2, (that is to say, only 1, 2, 4, 8, 16 … 2^13 are valid value of the happiness)

Summer Training has N (1 <= N <= 20000) days. Yangyang have a threshold of happiness Ti (1 <= Ti <= 20000) at the i-th day. If the total happiness of the day is greater than or equal to Ti, this day will be a happy day for her. Yangyang wants to maximize the number of happy days, but she doesn’t know how to achieve the idea, so again she come to ask you for help, can you make her happy?

Input

There are multiple test cases.

In each test case, the first line contains two postive integers N,M, separated by a space, where N indicates the number of days, and M indicates the number of ACMers

The following N lines, each will contain a integer, the i-th integer indicates the threshold of happiness for the i-th day.

The following M lines, each will contain a integer, the i-th integer indicates the happiness which the i-th ACMer will bring to her.

Output

For each test case ,output an integer, the maximum number of happy days.

Sample Input

1 2

2

1

1

3 2

1

3

4

2

8

Sample Output

1

2

反思

由于Happy值只能是二的倍数,所以具有一个特性,不存在多个小的能组成比某个大的值更大的值而不能被大的值所替代的情况。于是就能够贪心来做,首先二分枚举可能的值mid,将所需要的happy值小的mid个放入优先队列中,然后将happy值从大到小的放到最大的天里面,放入happy值后,该天数所需happy值减小,将其放入队列中。逐步得到答案。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include<vector>
using namespace std;

const int MAXN = 20010;  
int happy[MAXN],day[MAXN];  
int n, m; 

inline bool judge(int mid){
    priority_queue<int> que;  
    while(!que.empty())que.pop();  
    for(int i=1;i<=mid; i++){
        que.push(day[i]);  
    }
    int i;  
    i=1;  
    while(!que.empty()){
        if(i>m) break;  
        int temp = que.top();  
        que.pop();  
        temp -= happy[i++];  
        if(temp > 0) que.push(temp);  
    }
    if(que.empty()) return 1;  
    else return 0;  
}

bool cmp(int a, int b){
    return a>b;  
}
int main(){
    freopen("2.txt", "r", stdin);  
    while(~scanf("%d%d", &n, &m)){
        for(int i=1;i<=n; i++){
            scanf("%d", &day[i]);  
        }
        for(int i=1;i<=m; i++){
            scanf("%d", &happy[i]);  
        }
        sort(day+1, day+n+1);  //排序
        sort(happy+1, happy+m+1,cmp);  
        int left=0,right=n;   
        int ans;  
        while(left <= right){
            int mid = (left+right)/2;  
            if(judge(mid)) left=mid+1, ans=mid;  
            else right=mid-1;  
        }
        printf("%d\n",ans);  
    }
}

标准题解



代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <vector> 
#include <queue> 
#include <algorithm>

using namespace std;

const int maxn = 20000;

int H[maxn], T[maxn];
int N, M, loc;

bool greedyCheck(){
    priority_queue<int> pQ;

    for(int i = 0; i < loc; i ++){
        if(T[i] > 0){
            pQ.push(T[i]);
        }
    }

    int Htop = M;

    while(pQ.empty() == false){
        Htop --;
        if(Htop < 0)break;

        int p = pQ.top();

        pQ.pop();

        int oldP = p;
        p = max(0, p - H[Htop]);

        if(p > 0){
            pQ.push(p);
        }
    }

    return pQ.empty();
}

int binarySearch()
{
    int i;
    sort(T, T+N);
    sort(H, H+M);

    int ans;
    int left, right, mid;

    ans = 0;
    left = 0;
    right = N;
    while(left <= right){
        mid = (left + right)/2;
        loc = mid;
        if(greedyCheck()){
            left = mid + 1;
            ans = max(ans, mid);
        }
        else {
            right = mid - 1;
        }
    }
    return ans;
}

bool GetData(){
    if(scanf("%d %d", &N, &M) == EOF)return false;

    int i;

    for(i = 0; i < N; i ++){
        scanf("%d", &T[i]);
    }
    for(i = 0; i < M; i ++){
        scanf("%d", &H[i]);
    }
    return true;
}

int main(){
    while(GetData()) {
        printf("%d\n", binarySearch());
    }

    return 0;
}
赞 (0)

发表评论