HDU 6781 Solo (贪心 + 优先队列)

Solo

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 115    Accepted Submission(s): 51

Problem Description

Alice 和 Bob 准备 solo 一场算法竞赛。

比赛一共有 n 个题，编号为 1,2....,n，对于第 i 道题，Alice 需要 a[i] 分钟写出一份正确的代码，Bob 需要 b[i] 分钟写出一份正确的代码。

比赛规则为
1. 每道题第一个通过的人积 1 分，如果两人同时 AC 该题，只有 Alice 得分。
2. 比赛时长为 1018 分钟。

Alice 和 Bob 的比赛策略都满足：决定要去做某道题后，会一直解决该题，直到自己或者对手 AC 此题，如果对手 AC 该题，则会立即放弃这题。

Bob 写完一份正确的代码后会立即提交，但 Alice 写完一份正确的代码，可以先暂时不交题，等之后再交（交题的时间忽略不计，任何时间都可以交题）。

另外 Alice 知道 Bob 是按 1,2,....,n 的顺序来依次做题，知道每道题自己需要的时间和 Bob 需要的时间（即 a 序列和 b 序列）。

输出 Alice 最优策略下最多得几分。

Alice 和 Bob 想题都不需要时间。

 

Input

第一行一个整数 t(1≤t≤10) 表示 t 组数据。

每组数据第一行一个整数 n(1≤n≤2000) 表示题数。

第二行 n 个整数，表示 a[1],a[2],...a[n](1≤a[i]≤1000000000)。

第三行 n 个整数，表示 b[1],b[2],...b[n](1≤b[i]≤1000000000)。

保证至多只有一组数据 n>100。

 

Output

对于每组数据，一行一个整数表示答案。

 

Sample Input

2 6 6 6 6 6 6 6 1 1 1 1 1 1 3 1 2 3 5 1 1

 

Sample Output

1 3 样例解释 Case 1 开场直接 rush 最后一题。 Case 2 [0,1) 写掉第一题，第 5 分钟交；[1,3) 写第二题第 6 分钟交，[3,6) 写第三题第 6 分钟交。

 

Source

2020 年百度之星·程序设计大赛 - 初赛二

 

Recommend

heyang

 

Statistic | Submit | Discuss | Note

析：这个题和官方题解也不一致，没有使用动态规划，由于Alice可以做出题不提交，那么最优的策略一定是和Bob一起提交，所以Bob的每个题的提交时间都是固定的，然后只需要计算出Alice每个题的最晚结束时间，然后放到一个优先队列中，时间最长的在最顶层，然后对于每个题，先考虑能不能正常完成，如果能够按照做完，则直接放到队列中，如果不能，则需要比较队列中时间最长的题目比较，如果删除那个最长的题目，能够把当前的题目做出来，就把以前的题目删掉，把当前的题目放进去，为什么呢，因为当前题目比较短，可以为后面的题目提供更多的时间，这个策略就是最优的，最后队列中的所有题目都是能得到积分的。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#include <list>
#include <assert.h>
#include <bitset>
#include <numeric>
#include <unordered_map>
#define debug() puts("++++")
#define print(x) cout<<(x)<<endl
// #define gcd(a, b) __gcd(a, b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fi first
#define se second
#define pb push_back
#define sqr(x) ((x)*(x))
#define ms(a,b) memset(a, b, sizeof a)
#define sz size()
#define be begin()
#define ed end()
#define pu push_up
#define pd push_down
#define cl clear()
#define lowbit(x) -x&x
#define all 1,n,1
#define FOR(i,n,x)  for(int i = (x); i < (n); ++i)
#define freopenr freopen("in.in", "r", stdin)
#define freopenw freopen("out.out", "w", stdout)
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const LL LNF = 1e17;
const double inf = 1e20;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 2e3 + 7;
const int maxm = 2000000 + 7;
const LL mod = 1e9 + 7;
const int dr[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dc[] = {0, 0, 1, -1, 1, -1, 1, -1};
int n, m;

inline bool is_in(int r, int c) {
  return r >= 0 && r < n && c >= 0 && c < m;
}
inline int readInt(){
  int x;  scanf("%d", &x);  return x;
}

LL a[maxn], b[maxn];

unordered_map<int, int> mp;

struct Task{
  LL l, r, len;
  bool  operator < (const Task &t) const{
    if(len != t.len)  return len < t.len;
    if(r != t.r)  return r > t.r;
    return l > t.l;
  }
};

int main(){
  int T;  scanf("%d", &T);
  while(T--){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)  scanf("%lld", a + i);
    for(int i = 1; i <= n; ++i)  scanf("%lld", b + i), b[i] += b[i-1];
    priority_queue<Task> pq;
    LL time = 0;
    for(int i = 1; i <= n; ++i){
      if(a[i] + time <= b[i]){
        pq.push((Task){time, a[i]+time, a[i]});
        time += a[i];
      }
      else if(!pq.empty()){
        Task t = pq.top();
        if(time + a[i] - t.len <= b[i]){
          pq.pop();
          pq.push((Task){time-t.len, time-t.len+a[i], a[i]});
          time += a[i] - t.len;
        }
      }
    }
    printf("%d
", pq.sz);


  }
  return 0;
}