Sgu/551 2015年2月21日 (六) 22:48云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
Preparing Problem	★☆☆☆☆	答案正确	100	2015-2-21 22:47:52	t1,t2写错（2）

（AC 538）

题意

两个人共需要完成n份任务，完成一份任务各需要时间，两人同时做。完成一个任务时，若任务总数尚未到达n则继续做（即使做这份任务过程中对方完成了n份，也不会被打断）。问最终完成任务停止时，完成的任务数和用时。

题解

• 有点多线程的感觉，直接想有点复杂，一开始还联想到gcd、lcm之类的东西，后来发现完全没有关系。
• 我们容易画出示意图，e.g.

工作A.0---1---2---3---4---5---6---7---
工作B.0----------1----------2----------
任务T.0---1---2--34---5---6-7-8---9---

• 在例子中，假设我们要完成5份任务，那么在A4的时候就完成了，但是B未做完，也要完成到B2。
• 容易知道类似的情形，A、B不同时完成任务的时候，实际上最终完成的任务数量为n+1，当一方完成任务的时候，要看另一方的时间。
• 而A、B同时完成任务时，容易知道实际最终完成的任务恰好为n。
• 由于题目数据量并不大，线性枚举时间点T就可以AC，进一步优化可以尝试二分算法。

代码

551.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; #define si(n) scanf("%d",&n) #define ci const int & #define dsi(n) int n;si(n) #define f(i,n) for(int i=1;i<=n;++i) #define fi(i,p,n) for(int i=p;i<=n;++i) #define fd(i,n) for(int i=n;i!=0;--i) #define fdi(i,p,n) for(int i=n;i>=p;--i) int main() { dsi(n);dsi(t1);dsi(t2); int i1=0,i2=0; while(1) { if(i1/t1+i2/t2>=n)//fixed:t1,t2// if(i1==i2) { cout<<n<<" "<<i1; return 0; } else if(i1<i2) { cout<<n+1<<" "<<i1+t1; return 0; } else { cout<<n+1<<" "<<i2+t2; return 0; } if(i1+t1<i2+t2) i1+=t1; else i2+=t2; } return 0; }