首页 > 代码库 > 2014多校联合训练第一场（组队训练）
2014多校联合训练第一场（组队训练）
这是我、potaty、lmz第二次训练，毕竟经验不足，加上水平不够，导致我们各种被碾压。
A - Couple doubi:
这道题是道比较水的数论。但我们都没想出来要怎么做。后来是potaty提议打个表看看，然后lmz打出表后发现了规律。我还没细看，待研究后再补全。
D - Task：
这道题一看就知道是个贪心（现在只要是有deadline的题我都觉得是贪心了）。虽然想出来了，但还是不会严格证明为什么只要取满足task的且y最小（y相等时x最小）的machine就行了。
我的做法是把所有machine放进第machine_i_y个桶中，这个桶用set来实现。然后按照x的大小顺序从大到小（x相等时y从大到小）依次取task，每次找到满足最合适的machine。最合适的machine条件上面已经给出（貌似先看x最小，再看y最小也行，不过我的for每个machine再for每个y，如果改成for每个x，时间过不去）。但为什么task是从大到小来取呢？
题目中钱的公式是500*xi+2*yi，而yi<=100，xi>1。可以发现，只要xi>xj，即xi>=xj+1，那么无论怎么取yi和yj，500*xi+2*yi始终是大于500*xj+2*yj的。所以这样取task能保证钱是最多的。鉴于每个machine只能取一个task，如果不取x（或y）偏大的task，而去取x（或y）较小的task，这明显是一种对money的浪费，而且也没有完成更多的task，所以不会有上述做法的反例存在。综上，上述做法是对的。
第一次写博客，若有不明白的可以指出，我会尽力解答的。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <queue> 5 #include <algorithm> 6 #include <set> 7 #include <utility> 8 #define FOR(i,l,r) for(int i=(l);i<=(r);i++) 9 #define FORD(i,r,l) for(int i=(r);i>=(l);i--)10 #define rep(i,n) for(int i=0;i<(n);i++)11 using namespace std;12 typedef long long LL;13 14 pair<int,int> mac[100001],task[100001];15 int n,m;16 int main(){17 while (~scanf("%d%d",&n,&m))18 {19 FOR (i,1,n) scanf("%d%d",&mac[i].second,&mac[i].first);20 sort(mac+1,mac+1+n);21 FOR (i,1,n) swap(mac[i].second,mac[i].first);22 FOR (i,1,m) scanf("%d%d",&task[i].first,&task[i].second);23 sort(task+1,task+1+m);24 25 multiset<int> q[101];26 multiset<int>::iterator it;27 FOR (i,1,n) q[mac[i].second].insert(mac[i].first);28 LL ans=0; int ansgs=0; int j;29 FORD (i,m,1)30 {31 for (j=task[i].second; j<=100; j++)32 {33 if (!q[j].empty())34 if ((it=q[j].lower_bound(task[i].first)) != q[j].end())35 break;36 }37 if (j==101) continue;38 q[j].erase(it);39 ansgs++;40 ans+=500*task[i].first+2*task[i].second;41 }42 /*bool vis[100001];43 FORD (i,m,1)44 {45 FOR (j,1,n)46 if (mac[j].first>=task[i].first&&mac[j].second>=task[i].second&&!vis[j])47 {48 vis[j]=1; ansgs++;49 ans+=500*task[i].first+2*task[i].second;50 break;51 }52 }*/53 cout<<ansgs<<" "<<ans<<endl;54 }55 return 0;56 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。