Schedule HDU - 6180 (multiset , 贪心)
There are N schedules, the i-th schedule has start time si and end time ei (1 <= i <= N). There are some machines. Each two overlapping schedules cannot be performed in the same machine. For each machine the working time is defined as the difference between timeend and timestart , where time_{end} is time to turn off the machine and timestart is time to turn on the machine. We assume that the machine cannot be turned off between the timestart and the timeend.
Print the minimum number K of the machines for performing all schedules, and when only uses K machines, print the minimum sum of all working times.
Input
The first line contains an integer T (1 <= T <= 100), the number of test cases. Each case begins with a line containing one integer N (0 < N <= 100000). Each of the next N lines contains two integers si and ei (0<=si<ei<=1e9).
Output
For each test case, print the minimum possible number of machines and the minimum sum of all working times.
Sample Input
1
3
1 3
4 6
2 5
Sample Output
2 8
题意:
思路:
先把每一个任务按照起始时间排序,然后用一个multiset维护每一个机器在做任务的终止时间,
对于每一个任务,我们去multiset中去二分找是否有一个机器的任务终止时间在当前任务开始时间之前(或等于)。
如果有,就在那个机器中执行该任务,否则就创建一个新机器。
细节见代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int* p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int t;
struct node
{
int l, r;
} a[maxn];
bool cmp(node &aa, node &bb)
{
// if(aa.r!=bb.r)
// return aa.r<bb.r;
// else
return aa.l < bb.l;
}
int n;
multiset<int> st;
ll ans = 0ll;
int main()
{
//freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
//freopen("D:\\common_text\code_stream\\out.txt","w",stdout);
gg(t);
while (t--)
{
gg(n);
repd(i, 1, n)
{
gg(a[i].l);
gg(a[i].r);
}
sort(a + 1, a + 1 + n, cmp);
st.clear();
ans = a[1].r - a[1].l;
st.insert(a[1].r);
repd(i, 2, n)
{
auto it = st.upper_bound(a[i].l);
if (it == st.begin())
{
st.insert(a[i].r);
ans += a[i].r - a[i].l;
} else
{
it--;
ans += a[i].r - (*it);
st.erase(it);
st.insert(a[i].r);
}
}
cout << sz(st) << " " << ans << endl;
}
return 0;
}
inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
}
else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}
最新文章
- 解决pip安装超时
- 《Linux内核分析》期末总结
- 使用EasyUI布局时出现混乱瞬间的解决方法
- dbo与db_owner区别
- BP神经网络算法学习
- 日期选择器——java
- Spring Boot 学习笔记--整合Thymeleaf
- 2017 Multi-University Training Contest - Team 9 1005&;&;HDU 6165 FFF at Valentine【强联通缩点+拓扑排序】
- 在C#中几种常见数组复制方法的效率对比
- Algorithm -->; 爬楼梯求最大分数
- sqlmap常用渗透方法
- Linux如何挂载U盘
- D - Laying Cables Gym - 100971D (单调栈)
- SQL中的where条件,在数据库中提取与应用浅析
- java代码-----indexOf()方法--从字符串的某个字符的第一次出现的位子开始
- Spring下集成ActiveMQ推送
- plpgsql insert 性能 测试
- .NET控件命名规范
- 【bzoj1596】[Usaco2008 Jan]电话网络 树形dp
- CF678D(Iterated Linear Function)