HDU1789

题目链接

传送门

题目大意

题意是说先输入T,代表T组测试样例。每组样例输入n,接下来两行输入,第一行输入每份作业的截止日期, 第二行输入每份作业超过截止日期会扣的分数。求扣的最少分数。

解题思路

按照扣分从大到小排个序,优先考虑扣分多的。对于扣分多的作业,最好让它离截止日期越近越好(在截止 日期之前筛选)。vis数组起标记作用,最开始初始化为0,然后哪天被用了,就把哪天标记为1。把无论如何也不 能按时完成的那些扣得分数加起来(通过flag判断)。

参考代码

#include <functional>  
#include <algorithm>  
#include <iostream>  
#include <fstream>  
#include <sstream>  
#include <iomanip>  
#include <numeric>  
#include <cstring>  
#include <cassert>  
#include <cstdio>  
#include <string>  
#include <vector>  
#include <bitset>  
#include <queue>  
#include <stack>  
#include <cmath>  
#include <ctime>  
#include <list>  
#include <set>  
#include <map>  
#define REP0(i, n) for (int i=0;i<int(n);++i)  
#define REP1(i, n) for (int i=1;i<=int(n);++i)  
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)  
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)  
using namespace std;  
#define REP(i, n) for (int i=0;i<int(n);++i)  
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)  
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)  
#define REP_1(i, n) for (int i=1;i<=int(n);++i)  
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)  
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)  
#define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i)  
#define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i)  
#define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i)  
#define REP_N(i, n) for (i=0;i<int(n);++i)  
#define FOR_N(i, a, b) for (i=int(a);i<int(b);++i)  
#define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i)  
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)  
#define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i)  
#define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i)  
#define REP_1_N(i, n) for (i=1;i<=int(n);++i)  
#define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i)  
#define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i)  
#define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i)  
#define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i)  
#define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i)  
#define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i)  
#define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i)  
#define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i)  
#define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it)  
#define REP_S(it, str) for (char*it=str;*it;++it) // 用于字符串的 .. .  
#define REP_G(it, u) for (int it=hd[u];it;it=suc[it]) // 用于图论的 .. .  
#define DO(n) for ( int ____n ## __line__ = n; ____n ## __line__ -- ; )  
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)  
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)  
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)  
#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)  
#define PB push_back  
#define MP(A, B) make_pair(A, B)  
#define PTT pair<T, T>  
#define fi first  
#define se second  
#define Display(A, n, m) {                      \  
    REP(i, n){                                  \  
        REP(j, m) cout << A[i][j] << " ";       \  
        cout << endl;                         \  
    }                                           \  
}  
#define Display_1(A, n, m) {                    \  
    REP_1(i, n){                                \  
        REP_1(j, m) cout << A[i][j] << " ";     \  
        cout << endl;                         \  
    }                                           \  
}  
typedef long long LL;  
typedef double DB;  
typedef unsigned UINT;  
typedef unsigned long long ULL;  
const int dx[] = {-1, 0, 1, 0};  
const int dy[] = {0, 1, 0, -1};  
const int MOD = 1000000007;  
const int INF = 0x3f3f3f3f;  
const LL INFF = 1LL << 60;  
const DB EPS = 1e-9;  
const DB OO = 1e15;  
const DB PI = acos(-1.0); //M_PI;  

struct node  
{  
    int date;  
    int score;  
}q[1000010];  
int vis[1000010];  

bool cmp(node a ,node b)  
{  
    return a.score > b.score;  
}  

int main()  
{  
    #ifdef ZH  
    freopen("in.txt","r",stdin);  
    #endif  

    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        int n;  
        scanf("%d",&n);  
        FOR_1(i , 1 , n)  
        {  
            scanf("%d",&q[i].date);  
            vis[i] = 0;  
        }  
        FOR_1(i , 1 , n)  
            scanf("%d",&q[i].score);  
        sort(q + 1 , q + n + 1 , cmp);  
        int sum = 0;  
        FOR_1(i , 1 , n)  
        {  
            int flag = 0;  
            DWN_1(j , q[i].date , 1)  
            {  
                if(!vis[j])  
                {  
                    vis[j] = 1;  
                    flag = 1;  
                    break;  
                }  
            }  
            if(!flag)  
                sum += q[i].score;  
        }  
        printf("%d\n",sum);  
    }  
}  

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

© 2018-2019 惜春令 京ICP备18010644号 网站地图