首页 > ACM题库 > HDU-杭电 > HDU 1701 ACMer-贪心-[解题报告] C++
2013
12-21

HDU 1701 ACMer-贪心-[解题报告] C++

ACMer

问题描述 :

There are at least P% and at most Q% students of HDU are ACMers, now I want to know how many students HDU have at least?

输入:

The input contains multiple test cases.
The first line has one integer,represent the number of test cases.
The following N lines each line contains two numbers P and Q(P < Q),which accurate up to 2 decimal places.

输出:

For each test case, output the minumal number of students in HDU.

样例输入:

1
13.00 14.10

样例输出:

15

题目地址:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2267

直接贪心,从小到大排序,然后比较就ok了

代码如下:

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;

int i,j;
const int N=20010;
typedef long long LL;

int a[N],b[N];
int n,m;

int main()
{
    while(scanf("%d%d",&n,&m)&&(n+m)!=0)
    {

        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<m;i++)
            scanf("%d",&b[i]);
        sort(a,a+n);
        sort(b,b+m);
        int sum=0,cur=0;
        for(i=0,j=0;i<n;i++)
        {
            while(b[j]<a[i]&&j<m)
            {
                j++;
            }
            if(j>=m)
                break;
            if(b[j]>=a[i])
            {
                cur++;
                sum+=b[j];
                j++;
            }
        }
        if(cur>=n)
            printf("%d\n",sum);
        else
            printf("Loowater is doomed!\n");
    }
    return 0;
}

/*
2 3
5
4
7
8
4
2 1
5
5
10
0 0
*/

解题报告转自:http://blog.csdn.net/xh_reventon/article/details/8943150


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的