我就觉得和入场次序无关.

原来可以不用模拟直接计算答案..

C++选手注意：

用scanf会0ms AC，用cin整体会用1000+ms

我们先假设所有人拿到的票都是座位No.1

这个时候需要争执次数是0+1+2+3+…+(k-1)

再来一个数据一个数据看：

第i个人入座时，其对应的座位号s[i]一定是目前为止最大的，而且1……s[i]-1的座位一定都有人了

因为s[i]前面都坐满了，如果他的座位号是1而不是s[i]，则他比从s[i]开始坐要多争执s[i]-1次

这个时候s[i]如果不是1,则它能减少的争执数是s[i]-1

所以需要在假设的基础下减去s[i]-1 (i=1,2,3,……k)

所以最后的公式为0+1+2+3+…+(k-1)-sum(s[i]-1) (i=1,2,3……k)

化简，即1+2+3+……k-s[1]-s[2]-……s[k]

那个证明真的正确？

如果票上写的有1 2 3 3 的话

按 1 2 3 3 的入场顺序显然比 1 3 2 3 的入场顺序吵架少

顺序 1 2 3 3 | 1 3 2 3

吵架 0 0 0 1 | 0 0 1 1

前面那些结论是如何'得证'的？

c++小心，用int会70%，剩下的30%需要用long long / __int64

对这种题目无语~~~耍人类型的~~~~

不过AC88道了~~~冲进前300了~~~纪念下~~~~~~~~~~~~~~~~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

快排后模拟可以过啊 不止60分(回楼下)

晕，本来高高兴兴发现又有一道简单题，一提交却只有70分，才知道要用int64，希望大家吸取我的教训.

无聊的人作无聊的题，我发现我很无聊

为什么快排后只有60分？？

一个无聊的夜晚又AC了一道无聊的题~~

这题也太...那个了吧......

测试结果

直接计算: Accepted

模拟查找过程: 70分

快速排序后模拟: 60分

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

楼下貌似这写错了

all=a+all-i;

是

all=all+i-a;

吧.................

c++果然就是比FP慢.........

数学方法...........

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 197ms

├ 测试数据 08：答案正确... 478ms

├ 测试数据 09：答案正确... 212ms

├ 测试数据 10：答案正确... 462ms

.............

本人证明了一下，发现顺序与座位无关！！！

这样就简单了。

题目好烂！！！

时间复杂度O(K) 空间复杂度100000。。。。。。。

如果1个数第一次出现置之不理 不是第一次出现

begin

inc(t);

ans:=ans+t-该数

end

实质上就是模拟让第1-n号的人先坐好

祥哥你强悍!!!---|证明太为一针见血了!!!

看着题目觉得不对劲呢……进来一看题解，发现这题目描述如此诡异……暴汗中~~

Accepted 有效得分：100 有效耗时：0ms

时间复杂度：O(k)

空间复杂度：O(1)

算法和胡晓样大牛类似。

证明:

如果1次也不吵,则有1,2....k.

而对有重复的t(

我晕。。乱写了个并查集，居然AC了

复杂度应该还是线性的，不过常数稍微大点

用C++的。。用PRINTF %LLD会出问题。。。

老老实实IOSTREAM中。。。