【UVA-815】解题报告（贪心，二分）

原始题目

题目大意

给出\(n \times m\)个\(10 \times 10\)底面积柱子的海拔，以及洪水的总体积，计算洪水覆盖后的海拔高度以及覆盖柱子的百分比。

解题思路

  • 首先\(n*m\)个柱子可以排序后看作一排。

  • 思路一（自己的）：二分猜答案

    先判断洪水是否会淹没所有柱子，如果不是的话那么二分下界为最低海拔，上界为最高海拔。二分答案判断 当前海拔下淹没体积是否达到总洪水体积（计算当前淹没体积的时候也需要二分查找，比较繁琐），这个思路 并没有很好的利用海拔随覆盖柱子数增多而增大的性质。

  • 思路二（网络大神）：简化后贪心

    先预处理成\(1 \times 1\)（或者说直接考虑高度），对柱子高度排序后，我们考虑洪水一定是从低到高填充，那么贪心的 让洪水只填充到当前的柱子，直至平均高度不高于下个柱子，这时候就是最终答案。（tql）

解题代码

  • 二分：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <set>
    #include <queue>
    #include <map>
    #include <vector>
    #include <stack>
    #include <iostream>
    #include <iomanip>
    #include <bits/stdc++.h>
    #define rep(i,a,n) for(int i=a;i<n;++i)
    #define per(i,a,n) for(int i=n-a;i>=a;--i)
    #define se second
    #define fi first
    #define pb push_back
    #define mp make_pair
    #define np next_permutation
    #define ms(x,a) memset((x),a,sizeof((x)))
    #define all(x) x.begin(),x.end()
    #define eps 1e-9
    #define INF 0x3f3f3f3f
    using namespace std;
    const int maxn=1e5+5;
    const int maxl=26;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef vector<int> vi;
    typedef pair<int,int> pii;

    double a[maxn];
    double sum[maxn]; 
    double allflood,maxa;
    int n,m;

    double check(double nowl, double allcubic){
    	int index=lower_bound(a,a+m*n,nowl)-a;
    //	cout<<"index="<<index<<"  ";
    	if(index==0) return allcubic;
    	double temp=index*nowl-sum[index-1];
    //	cout<<"temp="<<temp<<endl;
    	return allcubic-(10.0*10.0*temp);
    }
    int main(){
    	ios::sync_with_stdio(false);
    	int kase=1;
    	while(cin>>m>>n&&m+n){
    		maxa=-100000;
    		rep(i,0,m){
    			rep(j,0,n){
    				cin>>a[i*n+j];
    			}
    		}
    		sort(a,a+m*n);
    		sum[0]=a[0];
    		rep(i,1,n*m) sum[i]=sum[i-1]+a[i];
    		cin>>allflood;
    //		cout<<"mmin="<<a[0]<<"   mmax="<<a[n*m-1]<<endl;
    		//一共n*m个区域；
    		
    		cout<<"Region "<<kase++<<endl;
    		//先判断填满是不是够
    		double temp=10.0*10.0*(n*m*a[n*m-1]-sum[n*m-1]);
    		if(temp<allflood){
    			double ans=(allflood-temp)/(100.0*n*m)+a[n*m-1];
    			cout<<"Water level is "<<fixed<<setprecision(2)<<ans<<" meters."<<endl;
    			cout<<"100.00 percent of the region is under water."<<endl;
    			cout<<endl;
    			continue;
    		} 
    		
    		
    		//不够 
    		double l=a[0],r=a[n*m-1],mid=(l+r)/2.0;
    		double ans=check(mid,allflood);
    		while(abs(ans)>eps){
    			if(ans>0)  l=mid;
    			else r=mid;
    			mid=(r+l)/2.0;
    //			cout<<"mid="<<mid<<"  ";
    			ans=check(mid,allflood);
    		}
    		int index=lower_bound(a,a+m*n,mid)-a;
    		cout<<"Water level is "<<fixed<<setprecision(2)<<mid<<" meters."<<endl;
    		cout<<fixed<<setprecision(2)<<(double)index*100/(n*m)<<" percent of the region is under water."<<endl;
    		cout<<endl;
    	}
    }

  • 贪心：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <set>
    #include <queue>
    #include <map>
    #include <vector>
    #include <stack>
    #include <iostream>
    #include <iomanip>
    #include <bits/stdc++.h>
    #define rep(i,a,n) for(int i=a;i<n;++i)
    #define per(i,a,n) for(int i=n-a;i>=a;--i)
    #define se second
    #define fi first
    #define pb push_back
    #define mp make_pair
    #define np next_permutation
    #define ms(x,a) memset((x),a,sizeof((x)))
    #define all(x) x.begin(),x.end()
    #define eps 1e-9
    #define INF 0x3f3f3f3f
    using namespace std;
    const int maxn=1e5+5;
    const int maxl=26;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef vector<int> vi;
    typedef pair<int,int> pii;

    int n,m;
    int a[maxn];
    int main(){
    	ios::sync_with_stdio(false);
    	int kase=0;
    	while(cin>>n>>m&&n+m){
    		n*=m;
    		rep(i,0,n) cin>>a[i];
    		sort(a,a+n);
    		double ans;
    		cin>>ans;
    		ans/=100;
    		a[n]=INF;
    		int index=0;
    		rep(i,0,n){
    			ans+=a[i];
    			if(ans/(i+1)<=a[i+1]){
    				ans=ans/(i+1);
    				index=i+1;
    				break;
    			}
    		}
    		cout<<"Region "<<++kase<<endl;
    		cout<<"Water level is "<<fixed<<setprecision(2)<<ans<<" meters."<<endl;
    		cout<<fixed<<setprecision(2)<<(double)(index*100)/n<<" percent of the region is under water."<<endl;
    		cout<<endl;
    	}
    }

收获与反思

  • 代码长度和速度高下立判啊。合理尝试贪心、二分，选择合适方法