【NOIP十连测】[D3T1] 平均数

Qizy Fenwick Tree, 二分, 其他, 数据结构, 解题报告

题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/10/test3_problem.pdf
官方题解：http://oi.cyo.ng/wp-content/uploads/2016/10/solution.pdf

这题被挖出是大原题了：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1711
另外™鬼畜出题人硬生生把NOIP搞成NOI Professional有意思吗？
YLUL)A7V{OMTL8]~RL2VL$8

std也是二分，然后搞归并排序
不过我有一种更自然的方法，复杂度一样，常数较大：
首先求出前缀和，记为ai
二分最后的答案记为x
不难发现,平均值大于x的需要满足一下条件：\(\frac{{{a_i} – {a_j}}}{{i – j}} \le x\)
然后化简一下得到：\({a_i} – x \cdot i \le {a_j} – x \cdot j\)
换一句话来说，把ai-x*i作为新序列求逆序对的个数就好啦！
结果被卡常了…..
管他的，51nod上能过

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;
const double EPS = 0.00001;

LL arr[N],k;
double tmp[N];
int n,Rank[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int cnt[N],tot,lim;
	
	inline void init(int w){
		memset(cnt,0,sizeof(cnt));
		tot = 1; lim = n+1; 
		for (int i=w;i<=lim;i+=lowbit(i)) {
			cnt[i]++;
		}
	}
	
	inline int query(int sta) {
		int ret = 0;
		for (int i=sta;i;i-=lowbit(i)) {
			ret += cnt[i];
		}
		return tot - ret;
	}
	
	inline void insert(int w) {
		tot++;
		for (int i=w;i<=lim;i+=lowbit(i)) {
			cnt[i]++;
		}
	}
};

bool judge(double sta) {
	for (register int i=1;i<=n;++i) {
		tmp[i] = arr[i] - sta*i;
	}
	tmp[n+1] = 0;
	sort(tmp+1,tmp+1+n+1);
	for (register int i=0;i<=n;++i) {
		Rank[i] = lower_bound(tmp+1,tmp+1+n+1,arr[i]-sta*i) - tmp;
	} 
	LL ret = 0;
	BIT::init(Rank[0]);
	for (int i=1;i<=n;i++) {
		ret += BIT::query(Rank[i]);
		BIT::insert(Rank[i]);
	}
	return ret >= k;
}

int main(){
	n = read(); cin>>k;
	k = (LL)n*(n+1) / 2 - k + 1;
	for (int i=1;i<=n;i++) {
		arr[i] = arr[i-1] + read();
	}
	double L = 0, R = 1e9, mid;
	while (R - L > EPS) {
		mid = (L + R) / 2;
		if (judge(mid)) {
			R = mid;
		} else {
			L = mid;
		}
	}
	printf("%.4lf",(R+L)/2);
	return 0;
}

277 thoughts to “【NOIP十连测】[D3T1] 平均数”

  1. Greetings from Ohio! I’m bored at work so I decided to browse your blog on my iphone during lunch break.
    I enjoy the info you provide here and can’t wait to take a look
    when I get home. I’m amazed at how quick your blog loaded on my phone
    .. I’m not even using WIFI, just 3G .. Anyways, excellent blog!

    Reply

  4. Right here is the perfect webpage for anyone who
    hopes to understand this topic. You know a whole lot its almost hard to argue with
    you (not that I personally will need to…HaHa). You definitely put a brand new
    spin on a topic which has been written about for many years.
    Wonderful stuff, just wonderful!

    Reply

  6. Pretty section of content. I just stumbled upon your blog and in accession capital to assert that I acquire in fact enjoyed account your blog
    posts. Any way I’ll be subscribing to your augment
    and even I achievement you access consistently rapidly.

    Reply

  9. Hi there I am so grateful I found your website, I really found you by mistake,
    while I was looking on Yahoo for something else, Anyhow I am here now and would just like to say thank you for a marvelous post and a
    all round exciting blog (I also love the theme/design), I don’t have time
    to read through it all at the minute but I have book-marked it and also added your RSS feeds, so when I
    have time I will be back to read more, Please do keep up the superb job.

    Reply

  12. Superb blog! Do you have any helpful hints for
    aspiring writers? I’m planning to start my own website soon but I’m a little
    lost on everything. Would you advise starting with a free platform like
    Wordpress or go for a paid option? There are so many choices out
    there that I’m completely confused .. Any recommendations?
    Thank you!

    Reply

  13. Heya i’m for the first time here. I came across this board and I
    find It really useful & it helped me out much. I’m hoping to give something again and aid others such as you helped me.
    natalielise plenty of fish

    Reply

  14. Having read this I thought it was really informative.
    I appreciate you finding the time and energy to put this content together.
    I once again find myself personally spending way
    too much time both reading and leaving comments. But so
    what, it was still worthwhile!

    Reply

  15. Link exchange is nothing else but it is simply placing the
    other person’s webpage link on your page at suitable place and other
    person will also do similar in favor of you.

    Reply

  16. Magnificent beat ! I would like to apprentice at the same time as
    you amend your site, how could i subscribe for a weblog web
    site? The account helped me a appropriate deal.

    I were a little bit acquainted of this your broadcast offered shiny clear
    idea

    Reply

  21. Thanks for one’s marvelous posting! I genuinely enjoyed reading it, you may be a great author.I will be sure to bookmark your blog and may come back someday.
    I want to encourage you continue your great posts, have a nice day!

    Reply

  24. I am now not certain where you are getting your information, however good topic.
    I must spend some time studying much more or understanding more.
    Thank you for magnificent information I used to be looking for this information for my mission.

    Reply

  25. Very great post. I simply stumbled upon your weblog
    and wanted to mention that I’ve really loved surfing around your weblog posts.
    After all I will be subscribing in your rss feed and I hope you
    write again soon!

    Reply

  26. Hello, i read your blog occasionally and i
    own a similar one and i was just wondering if you get a lot
    of spam comments? If so how do you reduce it, any plugin or anything you can advise?
    I get so much lately it’s driving me mad so any assistance is very much appreciated.

    Reply

  27. naturally like your website however you have to test the spelling on quite a few of your posts.
    Many of them are rife with spelling issues and I in finding it very troublesome to tell the truth
    on the other hand I’ll certainly come again again.

    Reply

  29. Hmm is anyone else having problems with the pictures on this blog loading?
    I’m trying to figure out if its a problem on my
    end or if it’s the blog. Any feed-back would be greatly appreciated.

    Reply

  30. Yesterday, while I was at work, my cousin stole my iphone and tested to see if it can survive a 25
    foot drop, just so she can be a youtube sensation. My
    iPad is now destroyed and she has 83 views. I know this is totally off topic
    but I had to share it with someone!

    Reply

  32. Do you have a spam problem on this website; I also
    am a blogger, and I was wondering your situation; we have created some nice
    methods and we are looking to swap techniques with other folks,
    be sure to shoot me an e-mail if interested.

    Reply

  33. Hello! Someone in my Facebook group shared this site with us so I came to check it out.

    I’m definitely enjoying the information. I’m bookmarking
    and will be tweeting this to my followers! Wonderful blog and amazing design.

    Reply

  35. It’s the best time to make some plans for the future and it’s time
    to be happy. I’ve read this post and if I could I wish to suggest you
    few interesting things or suggestions. Maybe
    you could write next articles referring to this article.

    I want to read more things about it!

    Reply

  36. Excellent weblog here! Also your website a lot up very fast!
    What host are you the use of? Can I am getting
    your affiliate link on your host? I desire my website loaded up as fast as yours lol

    Reply

  39. Hey would you mind letting me know which hosting company you’re working with?
    I’ve loaded your blog in 3 completely different web browsers
    and I must say this blog loads a lot quicker then most. Can you recommend
    a good internet hosting provider at a fair price? Thanks, I appreciate it!

    Reply

  41. I’m really loving the theme/design of your weblog.
    Do you ever run into any web browser compatibility problems?
    A few of my blog readers have complained about my website not
    operating correctly in Explorer but looks great in Safari.
    Do you have any recommendations to help fix this issue?

    Reply

  45. After exploring a few of the blog articles on your web site, I honestly
    appreciate your way of blogging. I book marked it to
    my bookmark website list and will be checking back soon. Take a look at my web site
    too and let me know your opinion.

    Reply

  49. I’m extremely inspired together with your writing talents and also with the structure on your weblog.

    Is this a paid subject matter or did you customize it yourself?
    Anyway keep up the excellent quality writing, it’s rare to peer a nice blog like this one nowadays..

    Reply

  62. I know this if off topic but I’m looking into starting my own weblog and was curious what
    all is required to get setup? I’m assuming having a
    blog like yours would cost a pretty penny? I’m not very web savvy so I’m
    not 100% sure. Any tips or advice would be greatly appreciated.

    Many thanks

    Reply

  64. An outstanding share! I’ve just forwarded this onto a coworker
    who has been conducting a little homework on this. And he actually bought me dinner due
    to the fact that I found it for him… lol. So let me reword this….
    Thanks for the meal!! But yeah, thanx for spending the time to talk about this subject here on your web site.

    Reply

  71. We’re a group of volunteers and starting a new scheme in our community.
    Your web site provided us with valuable information to work on.
    You’ve done a formidable job and our entire community will be grateful to you.

    Reply

  101. Excellent blog here! Also your web site loads up fast!
    What host are you using? Can I get your affiliate link to your
    host? I wish my web site loaded up as fast as yours lol

    Reply

  105. Hey I know this is off topic but I was wondering if you knew of any widgets
    I could add to my blog that automatically tweet my newest twitter
    updates. I’ve been looking for a plug-in like this for quite some time and
    was hoping maybe you would have some experience with something like
    this. Please let me know if you run into anything. I truly enjoy
    reading your blog and I look forward to your new updates.

    Reply

  106. I wanted to thank you for this good read!! I certainly enjoyed every little bit of it.
    I have you saved as a favorite to check out new things you post…

    Reply

  114. Hello fantastic website! Does running a blog
    such as this take a lot of work? I’ve very little understanding of programming but
    I had been hoping to start my own blog in the near future.
    Anyway, should you have any ideas or techniques
    for new blog owners please share. I understand this
    is off subject but I just had to ask. Appreciate it!

    Reply

  121. Hi there! I could have sworn I’ve been to this
    blog before but after checking through some of the post I
    realized it’s new to me. Anyhow, I’m definitely happy I found it and I’ll
    be book-marking and checking back often!

    Reply

  142. You actually make it seem really easy along with your presentation but
    I find this matter to be really something that I believe I’d by
    no means understand. It kind of feels too complex and very huge for me.

    I’m taking a look forward for your next put up, I’ll
    try to get the hold of it!

    Reply

  144. Excellent blog you have here but I was curious if you knew of any message boards that cover the same topics discussed here?

    I’d really like to be a part of group where I
    can get advice from other experienced people that share the same interest.
    If you have any suggestions, please let me know. Bless you!

    Reply

  150. I loved as much as you will receive carried out right here.
    The sketch is tasteful, your authored subject matter stylish.
    nonetheless, you command get bought an impatience
    over that you wish be delivering the following. unwell unquestionably come further formerly again since exactly the same nearly a lot often inside case you shield this increase.

    Reply

  156. We’re a group of volunteers and starting a new scheme in our
    community. Your web site offered us with valuable info to work on. You’ve done a formidable job and our
    whole community will be thankful to you.

    Reply

  163. Hi, i believe that i saw you visited my web site so i came to return the prefer?.I’m attempting
    to in finding issues to improve my website!I suppose its
    adequate to make use of some of your ideas!!

    Reply

  167. I really like your blog.. very nice colors & theme. Did you create this
    website yourself or did you hire someone to do it for
    you? Plz reply as I’m looking to construct my own blog and would like to know where u
    got this from. cheers

    Reply

  179. The world is like a hillside. As long as you are not standing at the apex, someone will always be taller than you. When you look up for a long time, you must look down at the right time. We are all ordinary people.

    Reply

  180. Thanks for one’s marvelous posting! I seriously enjoyed reading it, you may be a great author.I will be sure to bookmark
    your blog and may come back in the future. I want to encourage continue your great writing, have a nice
    holiday weekend!

    Reply

  221. It’s appropriate time to make some plans for the future and it is time to be happy. I have learn this submit and if I may I desire to counsel you some interesting issues or suggestions. Perhaps you could write subsequent articles regarding this article. I want to learn even more things about it!

    Reply

  245. I loved as much as you’ll receive carried out right here. The sketch is tasteful, your authored material stylish. nonetheless, you command get bought an edginess over that you wish be delivering the following. unwell unquestionably come further formerly again since exactly the same nearly very often inside case you shield this hike.|

    Reply

  248. You are so cool! I do not believe I’ve read anything like that before. So nice to find another person with some genuine thoughts on this issue. Seriously.. thank you for starting this up. This site is something that is required on the web, someone with a bit of originality!|

    Reply

  262. I know this if off topic but I’m looking into starting my own weblog and was wondering what all is needed to get set up? I’m assuming having a blog like yours would cost a pretty penny? I’m not very internet savvy so I’m not 100 sure. Any tips or advice would be greatly appreciated. Thank you|

    Reply

  273. I like the valuable info you supply for your articles. I will bookmark your weblog and test once more right here frequently. I am fairly certain I’ll be informed plenty of new stuff right here! Best of luck for the next!|

    Reply

  276. Hello there, You’ve done a fantastic job. I’ll definitely digg it and personally recommend to my friends. I am confident they will be benefited from this site.|

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *