tea
【题目描述】有n个容量为V的瓶子，第i个瓶子中装着a[i]个单位的tea，使所有瓶子内的tea在不 超过其容量的前提下，非空的瓶子最少。在一个单位时间内，可以同时将多个瓶子中的tea倒入另外多个瓶子中但每个瓶只能倒出或倒入一个单位的tea，在使用最少瓶子的情况下，所消耗的时间最少。求出需要的瓶子数和最少时间。
这题反正也找不到地方交，那就不写什么输入输出了。数据范围的上限是1e5。
【题解思路】乍一眼感觉可做性挺强的。
- 明显要贪心。第一问直接用饮料的总容量判一下就好,记答案为m。第二问贪心选择最多tea的瓶子和最少tea的瓶子装在一起，这样可保证每个单位时间工作量最大，很明显需要排序成容量递减的瓶子。
- 脑中模拟一下这个过程，第一个单位时间内，将容量最多的和容量最少的倒一起，容量第二多的与容量第二少的到在一起……然后一轮下来之后，将倒满了的瓶子不算，继续重复上述过程。
- 火眼金睛看出这道题有没有什么端倪？这样一直首尾首尾倒下去，瓶子数会慢慢减少的吧，满瓶数量会越来越多，单调性？！我会二分。以编号为m的瓶子为下界，用k表示最多需要的单位时间内可完成任务。诶，这个k是不是有什么性质啊？我们已知最后完成任务需要m个瓶子，那么有：
（1） 倒完所需的时间一定要大于第m+1个瓶子的容量。
证明：因为第a[m+1]是m+1~n的瓶子里装tea最多的，每个单位时间只能从m+1的瓶中倒出一个单位的水，则至少需要a[m+1]的时间。
（2） 倒完所需时间还一定都小于V（可以容纳的最大容积）。
证明：设m+1~n的瓶中tea的总和为V_max，下面证明V_max< V。所有的tea之和为(V*(m-1),V*m], (sum)a[1~m] > m*a[m+1] >= m*k (sum)a[m+1~n] < (V-k)*m,即V_max = (V-k)*m >0,所以 V > k 。
此为理性理解，可能感性理解灰常容易，但是ve此刻只会理性分析。陷入其中无法自拔
4. 借此二分，下界为a[m+1]，上界为V。啪啪啪，正解就出来了，无再多细节之说。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,V,minn,l,r;
long long sum = 0;
int a[maxn];
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool v(int x){
sum = 0;
for(int i = 1;i <= minn; ++i) sum += min(V-a[i],x);
for(int i = minn+1;i <= n; ++i) sum -= a[i];
return sum >= 0;
}
bool cmp(int x,int y) {return x > y;}
int main(){
freopen("tea.in","r",stdin);
freopen("tea.out","w",stdout);
n = read(),V = read();
for(int i = 1;i <= n; ++i){
a[i] = read();
sum += a[i];
}
if(!(sum%V)) minn = sum/V;
else minn = sum/V + 1;
sort(a+1,a+n+1,cmp);
if(minn < n) l = a[minn+1];
else l = 0;
int r = V;
while(l + 1 < r){
int m = l+r>>1;
if(v(m)) r = m;
else l = m;
}
for(int i = l;i <= r; ++i)
if(v(i)) {
printf("%d %d
",minn,i);
return 0;
}
return 0;
}
这个题花了很长时间，因为题看错了 + sb错误没查出来。下面列出这题的sb错误以警示自己。
1.
if(!(sum%V)) minn = sum/V;
等价于sum%V==0，但不是 !sum%V，还有这句话可以写成：
minn = (sum + V -1)/V;
2. 循环的起始因为变量长得太像写错了，但这不是理由，以后要注意了。
3. 变量如果设一样的表不同意思一定要搞清楚什么时候变化之类的，切忌混淆。