{"id":1419,"date":"2013-03-22T20:40:58","date_gmt":"2013-03-22T12:40:58","guid":{"rendered":"https:\/\/blog.rexdf.org\/?p=1419"},"modified":"2013-03-22T20:40:58","modified_gmt":"2013-03-22T12:40:58","slug":"codeforces-175-c","status":"publish","type":"post","link":"https:\/\/blog.rexdf.org\/ja\/2013\/03\/codeforces-175-c\/","title":{"rendered":"Codeforces 175 C"},"content":{"rendered":"
\n
C. Building Permutation<\/div>\n
\n
time limit per test<\/div>\n

2 seconds<\/p><\/div>\n

\n
memory limit per test<\/div>\n

256 megabytes<\/p><\/div>\n

\n
input<\/div>\n

standard input<\/p><\/div>\n

\n
output<\/div>\n

standard output<\/p><\/div>\n<\/div>\n

\n

Permutation\u00a0p<\/i>\u00a0is an ordered set of integers\u00a0p<\/i>1<\/sub>,\u2009\u2009p<\/i>2<\/sub>,\u2009\u2009…,\u2009\u2009p<\/i>n<\/i><\/sub>, consisting of\u00a0n<\/i>\u00a0distinct positive integers, each of them doesn’t exceed\u00a0n<\/i>. We’ll denote the\u00a0i<\/i>-th element of permutation\u00a0p<\/i>\u00a0as\u00a0p<\/i>i<\/i><\/sub>. We’ll call number\u00a0n<\/i>\u00a0the size or the length of permutation\u00a0p<\/i>1<\/sub>,\u2009\u2009p<\/i>2<\/sub>,\u2009\u2009…,\u2009\u2009p<\/i>n<\/i><\/sub>.<\/p>\n

You have a sequence of integers\u00a0a<\/i>1<\/sub>,\u2009a<\/i>2<\/sub>,\u2009…,\u2009a<\/i>n<\/i><\/sub>. In one move, you are allowed to decrease or increase any number by one. Count the minimum number of moves, needed to build a permutation from this sequence.<\/p>\n<\/div>\n

\n
Input<\/div>\n

The first line contains integer\u00a0n<\/i>\u00a0(1\u2009\u2264\u2009n<\/i>\u2009\u2264\u20093\u00b7105<\/sup>) \u2014 the size of the sought permutation. The second line contains\u00a0n<\/i>\u00a0integersa<\/i>1<\/sub>,\u2009a<\/i>2<\/sub>,\u2009…,\u2009a<\/i>n<\/i><\/sub>\u00a0(\u2009-\u2009109<\/sup>\u2009\u2264\u2009a<\/i>i<\/i><\/sub>\u2009\u2264\u2009109<\/sup>).<\/p>\n<\/div>\n

\n
Output<\/div>\n

Print a single number \u2014 the minimum number of moves.<\/p>\n

Please, do not use the\u00a0%lld\u00a0specifier to read or write 64-bit integers in \u0421++. It is preferred to use the cin, cout streams or the\u00a0%I64dspecifier.<\/p>\n<\/div>\n

\n
Sample test(s)<\/div>\n
\n
\n
input<\/div>\n
2 3 0<\/pre>\n<\/div>\n
\n
output<\/div>\n
2<\/pre>\n<\/div>\n
\n
input<\/div>\n
3 -1 -1 2<\/pre>\n<\/div>\n
\n
output<\/div>\n
6<\/pre>\n<\/div>\n<\/div>\n<\/div>\n
\n
Note<\/div>\n
In the first sample you should decrease the first number by one and then increase the second number by one. The resulting permutation is\u00a0(2,\u20091).<\/p>\n
In the second sample you need 6 moves to build permutation\u00a0(1,\u20093,\u20092).<\/p>\n<\/div>\n
\r\n#include <iostream>\r\n#include <cstdio>\r\n#include <cstring>\r\n#include <algorithm>\r\n\r\nusing namespace std;\r\n\r\nlong long a[300005];\r\n\r\n\r\nint main()\r\n{\r\n    int n;\r\n    long long ans,tmp;\r\n    cin>>n;\r\n    for(int i=0;i<n;i++)cin>>a[i];\r\n    sort(a,a+n);\r\n    ans=0;\r\n    for(int i=0;i<n;i++)\r\n    {\r\n        tmp=(long long)(i+1)-a[i];\r\n        if(tmp<0)ans-=tmp;\r\n        else ans+=tmp;\r\n    }\r\n    cout<<ans<<endl;\r\n    return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
C. Building Permutation time limit per t … \u7d9a\u304d\u3092\u8aad\u3080 →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[3],"tags":[125],"class_list":["post-1419","post","type-post","status-publish","format-standard","hentry","category-algorithm","tag-codeforces"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/posts\/1419","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/comments?post=1419"}],"version-history":[{"count":0,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/posts\/1419\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/media?parent=1419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/categories?post=1419"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/tags?post=1419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}