2018.02.12 noip模拟赛T2

时间:2023-03-08 21:47:07

二兵的赌注

Description
游戏中,二兵要进入了一家奇怪的赌场。
赌场中有n个庄家,每个庄家都可以猜大猜小,猜一次一元钱。
每一次开彩前,你都可以到任意个庄家那里下赌注。
如果开彩结果是大,你就可以得到你之前猜大的庄家相应的ai元钱。
如果开彩结果是小,你就可以得到你之前猜小的庄家相应的bi元钱。
你可以在同一个庄家那里既猜大又猜小,(这样是两块钱),也可以什么都不猜(这样不用钱)。
问怎么样下注,才能赢得最多的有保障的钱。
有保障的钱指不管开彩结果是大是小,你都能够赢得相应的钱。
你能帮助他计算这个值吗?
Input
第一行一个数字N。表示有N个庄家。
接下来N行,每行2个实数,分别表示这个庄家的ai和bi。
Output
一个四位小数,表示最多能赢的有保障的钱。
Sample Input
4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5
Sample Output
0.5000
HINT
样例中,最好的策略是赌第一个庄家开小,第三、第四个庄家开大
测试点 N
1 N≤10

2
3 N≤1000

4
5
6
7 N≤100000
8
9
10

1.0 ≤ ai, bi ≤ 1000.0

1s/128M

好了,拿到题先花一定的时间弄清题意。

然后我们就会发现:押大小和哪个庄家之间完全没有关系,一个庄家的大和小完全是独立的。继续分析,显然押越大的越好。

于是我们分别sort一下。

然后我开始了分析:首先读入时-=1,然后,设大或小为a[]和b[],分别取前i.j个押。

然后对于每对确定的i,j,易知s=min(suma[i]-j,sumb[j]-i)其中sum为前缀和。

我们设suma[i]-j=左,sumb[j]-i=右

然后定性分析:

当j固定时,i+则左+右-,i-则左-右+

当i固定时,j+则左-右+,j-则左+右-

再次分析可知对于一对(i,j),若i+,则可能存在的ans>s必须令j+

于是有了以下思路:for(i:1...n) 对于每个i找到匹配的j,则i++时j不用从头开始枚举,只需继续j++,于是时间复杂度O(n)完成(不记sort)

以上是我在考场上的思路。不管思考过程多么艰难以至于花费1hour才想出来,但是结果就是,和标准程序简直一模一样。但是代码实现上就很naive了。

同一个思路,我代码实现起来写了都要40+行,再一看标程,不到十行就解决了,尴尬......

我的代码大概是这样

 #include <cstdio>
using namespace std;
int a[],b;
void c();
int main()
{ ///读入
///sort一波
/**
for(i:1...n)
{
ax=xx
bx=xx
c=xx
while(j<=n && j<=c+a[i])
{
if(xXX)
xxx
else if(xxx)
xxx
else
xxx
}
d=xx
e=xx
f=xx
}
*/
return ;
}

my code

瞎设变量,大概近十个。

然后结果就是:推了一小时,打了半小时,最后又调了半小时。结果还是错的跟翔一样。

还有一个很奇怪的事:scanf读入double会出现蜜汁读入0,int就好得很。只好用cin缓慢读入了。找时间问一下雨菲,她肯定又不会理我。。。

那么来看看标程:

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <math.h>
#include <queue>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <ctime>
using namespace std; #define ALL(c) (c).begin(),(c).end()
#define IN(x,c) (find(c.begin(),c.end(),x) != (c).end())
#define REP(i,n) for (int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define INIT(a,v) memset(a,v,sizeof(a))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
template<class A, class B> A cvt(B x) { stringstream ss; ss<<x; A y; ss>>y; return y; } typedef pair<int,int> PII;
typedef long long int64; int n=;
double a[],b[]; int main() {
freopen("coin.in","r",stdin);
freopen("coin.out","w",stdout);
cin >> n;
REP (i,n) {
cin >> a[i] >> b[i];
a[i]-=; b[i]-=;
}
sort(a,a+n); reverse(a,a+n);
sort(b,b+n); reverse(b,b+n);
int i=,j=;
double r=;
double sa=,sb=;
while (i<n) {
sa+=a[i];
i++;
while (j<n && min(sa-j,sb-i)<min(sa-(j+),(sb+b[j])-i)) {
sb+=b[j];
j++;
}
r=max(r, min(sa-j,sb-i));
}
printf("%.4f\n",r);
return ;
}

标程

那么我们忽略上面一长串的头文件和宏定义。仔细观察关键部分可以发现:我那冗杂的程序和变量得到了极大的简化,强!喵!喵不可言啊!

接下来是文字答案中的二分,利用了单调性。

给出来:

Coin
算法零:
输出0即可。
算法一:
直接O(4^n)暴力枚举,期望得分20分。
算法二:
贪心,问题所求的是最大化min(∑ai ?na ?nb,∑bj ?na ?nb),na, nb分别表示猜大猜小的个数。将ai, bi全部减一,所求变为min(∑ai ?nb,∑bj ?na)。我们枚举na, nb,贪心取最大的na个ai和nb个ai即可。
复杂度O(n^2),期望得分60分
算法三:
贪心+二分,假设na固定,那么ai的选取也是确定的。假设nb从0开始一个个往上增加,∑bj –na递增,∑ai –nb递减。min(∑ai ?nb,∑bj ?na) 在∑bj –na超过∑ai –nb前递增。所以只需二分∑bj –na什么时候超过∑ai –nb即可。
复杂度O(n log n),期望得分100分。
标程:
直接sort+O(n)
思路跟我的一样可惜我TM写了30-40行的东西他十行不到搞定。
仍需努力呀。

我自己打了测了一下,最大的一个数据正确,但是跑了1.2s还是1.4s(算上了编译时间)

我的代码:

 #include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=;
int n;
double ans=-;
double a[N],b[N];
double suma[N],sumb[N];
bool cmp(double a,double b){return a>=b;}
int tw_divide(int l,int r,int i)
{
if(l==r) return r;
int mid=(l+r)>>;
double now=min(suma[i]-mid,sumb[mid]-i);
double nowl=min(suma[i]-mid+,sumb[mid-]-i);
double nowr=min(suma[i]-mid-,sumb[mid+]-i);
if(now>=nowl && now>=nowr) return mid;
if(now<nowl) return tw_divide(l,mid-,i);
if(now<nowr) return tw_divide(mid+,r,i);
}
int main()
{
freopen("coin.in","r",stdin);
//freopen("coin.out","w",stdout);
scanf ("%d",&n);
for(int i=;i<=n;i++)
{
cin>>a[i]>>b[i];
a[i]-=;b[i]-=;
}
sort(a+,a+n+,cmp);
sort(b+,b+n+,cmp); for(int i=;i<=n;i++)
{
suma[i]=suma[i-]+a[i];
sumb[i]=sumb[i-]+b[i];
}
double now;
int j;
for(int i=;i<=n;i++)
{
j=tw_divide(,n,i);
now=min(suma[i]-j,sumb[j]-i);
ans=max(ans,now);
}
printf("%.4f",ans);
return ;
}

my code

我还是比较喜欢第一种。二分时间多个logn而且还难得写。