http://codeforces.com/contest/1151/problem/D
题意:
n个学生,每个学生都有自己的位置,最后要使
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAOwAAAAiCAIAAADTU6KHAAAJkUlEQVR4Ae1cf1RT1x2/9vTsdQYH8fSFHUlAk7XY5QiDpc7ARIOWdGoRhsced5p2pww7pmxnuM1Tzlo2N2xZN2mttrgq1sOmx4ozWkmrLivoIIwpnLAw0Eo8JXSDdgtuhZnXQ09273tJSpL3Xt4PXhJO3/3n5d0f3x+f7/fe+70/XoCfLZ3ZqdVqd55hqyKkzNlk1mrNTU4hbed9G9+lp/O1Wn3JjqZjp06dOvTTilXLtcs3NvX55r1m/kSpdjeQU3wRwNbXnzms+tne1sM/f+sO+FyKJmfLc4d3b9Vj8RVDCm6JUm0B7P9S6CPTlBGIGwJ3xY2TzEhGQCIEZCeWCFiZbPwQkJ04fljLnCRCILmceOLSLmPxfpdEugog+5/zO/LLDw0QApomZZOkAziAkmt/sXHXpQmhmCXPxs641YJjhkZn4vaapobsnTci2MdFKntNBp6VlYUrANA3SLbzGBdVBPqTz9lowHCLdVxIeyCkkRRtxltLMczUPMJE2/VygQJgD/zyKlMFMflTHwx1t9SuzsBAbqMrkpDPXoMDvMYe4d2R1cS+Oxv0cCDCKtvFEmJoHwtghmZSZofbdKTZxOoBzJIkiRN7rRYl0NU5GB1ltNmETMzi5cw6spdYLZBuaoZ+GY4mMxon9vuR/YGunl//mRrq7vUw6hMlk6/tUcTf1DwaVTQXGTEBngsmPGlE2tTnqNMBrPyElycdf3I4sasxF4DCA4zDMNJq6oP3xrzcnYIvEH7kzAxO7PddrFbyhRfSo+0RDILZa5SQvabOwVAuLpsLwOI4CGodadORA4WA92jh9yfFwu7aqd86gaFivRa5EVNS4JkZygQda2EPbXlMSdjeuDDJJJ3Y/OtOB6JdkJ8nlhJde04A0zWUOC/SptpSiwmM/O7Na/z4JoMTD9qtI0BTYszmJ3pca+etXA0Im+2yRPsUk3/tuAr1MZlWStFN5wPAlDU1uUYNGLHaB3kZl4sTE2OdBy1GlUq1VJWm3nTwjaO12+vP3uLFhq3yZH+Xk3EMIt49XZ0DWaekaBO61aXM+ZoeEB29/WyaCC/r770CGy/6+ML3tSqVOi0lzbDrrbG56jAMAE+crdZCXO9JW9s0MD3W+avy+9XqpSr4bqg+/e5c8aaDhM2mefkFADi7+vlNebFiGZ9zH9oWMDRcm4JVx9seRaEbUNbYYzXkXE7Ga/QEXfsMCpIzWUeyVQ8pKltMDCtQqxCLlbNafGJiSj2AZdfY0FpwylYJUea7kmSUjBZgFObDmJ3irFCkGuo6yGWoo04DF7oCVleM7CMKYtiUXBvwWUxA8jFG4omzVetru2dML52sy4ebmCA9b/WX4QPbtA5G4IE0aatW37Mg53mmMwrY8eq31x/tY9rKvumCA3GmOj1IL/R0H6p5ZtFvEGfipms4lJ2YH5ovqiHjgev8JjpuslJDJTC/2rn/G2oYTygy788EYKTlDz1keykAJt5ubdE9sVk/MTYKeSz85rHzDWsQa7BQ8QUACPfoP7iJzrdWTJumq6HqTtdNPoRZr2ISf2qoav0Q9svtW7UUUeJvf0GxW0Fh/qex20K1cevjqsKK++j5el5/asuedwBom8zy7i+mr0Ofu2DF92zFjyDO/b0dcH7LffjrcJSISo49+dtavFHZERmLnzzR96wxInOuXv95/FvGuu5wav/7F/jvOfPSV8IRphWDCiZM5euDHfm9G6jPejxUv5cE4KLnbtjSMnv2WuHEnfuj3ZsDrD2OP8JuiuVkfylcm+CbWLA52jTIjuMzYrAPe22vJF21tDW0c0dtBPEb7V0vr0nFsIxKptMYch5nJUnNeVJtPwVUjhFOUFtwrGKGYYfqc6w9vM8AjTWrMjmlA2DYNxxOkuFNOMBRwHpbS6EoUkYTQR2iWAcKqHweYRtsdxeLrw+6rqL43rD2QTIOhj977KjjajYW6YnJ99+fJIiBQ+VGw/LFKeYWNyMh/c6O2z7f2OFgZ4+smK6B4+vMzCeR+aF3z5/fhgEHVlK4KpQV/x/EzMeQadaSJXPPergfzm7KIgM6sUNp8HK7B+pr+s7mbGkBDgC7dmUexRi4jzefg5w3bDUrpz8chQYO5M/9g9Gmn8zMQA/TBOckTpzZnHjJkixE4wFtNkWK6HnzJERXWbZulef1Ct3Tl//+0uMvaBqer0iZ7r/QB0uEJeW9UOLBYcbtDqKvC83U5rVSBQOcxL45Amd4DF8c7M+cGnGrtCgNEg0tCoie43DXHDPsefHb2kFJASZ634FhHjCXFAViw8G217qgfZ+sLldee8H4lQYUOUqTmG16axiGM+n38oKZzYmVG7eVQ/Xct27AHjk9fHRb6d4RqBOE232utXvDhvyPPl/8i6fAuVc9eOkT6+jCVU4IZOcaochD7usMtbvs5yF/04Y1vBRjIMaYPU3cQWUzdwjIjCaRYWrBgytoisRmFZY9hoPhrn4YARNjp6sgyrjl92d+kIN99G9JAe7qvAhFnwUstcrbZC4afeXHv1Y+s+OhgHOLVTC6PaNNr7uHYDcy5gbGTdTSWqPT6R5+cSCaSignGKPQP8evNJYtUyjwLBxfVtZ4Zehi7VdTMbghE4pwyQNZvLI9FDXT02HN9Z6AfQWzWOnPlKkAcVbEyEqLfyEVC4fwCPyI5EeGarw2vbjHxH6/z9lMwpyB4/cV154cQruZgSQdwKNHSjCgKDky67DfdQSJkYrja+qvCLpPFpQ6xpPRpj6rBbpC+AYf+bUy62fFIu9OkBArLVbH8Z8c7LodQ3TGYtKLldUX6byYWvVIvKhjlCxYIOBQn48TB9lEP6UHOJqn5DmMNiW1jfBhDtKIdGK0f6G0tLVV6zYem9WjOTAOq0KZ6lMvdlufrar64TF4tZj0HoDXdobVj/cLkoLvDTq3tbHZIWaCIpWUCOB4Awj5cbAp6QYCLr2KdGJv+3czMAWuL2sWeZedvO0YvMdGbe1hJQdsDQY4u4RilwRAj1iS2LLdE5VQLmkAllBgJtIcbEoOFaWt/OMYkU7MJLKAfHSijVEqeO27VyiAIjU1dVlEhCiArtgm6E58Yj84EatBoP0sgOeIIh8yMW2K7sQL/LQjeZwYLW8a4VWJRH6fFG0V9EmPQGijiSU6JxkBpjARJ1mS/XkKPEOZmEnLRB+bJUVKNnlEg5KkCsGjldt3pwu9L55kTizaSDKBzyACbIcdn0E4ZJXnIwKyE89Hq8kyhyEgO3EYHPLLfERAduL5aDVZ5jAEZCcOg0N+mY8I/B939iZibfpIsQAAAABJRU5ErkJggg==" alt="" />
最小,求最小的总和
题解:
开始各种排序(a,b同时排,a-b和a,b同时排),都不对,其实只要给ai-bi排序就行。。
代码:
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
long long a,b;
}stu[];
int cmp(const node x,const node y){
return (x.a-x.b)>(y.a-y.b);
}
int main(){
int n;
cin>>n;
for(int i=;i<n;i++){
cin>>stu[i].a>>stu[i].b;
// a[i]=stu[i].a-stu[i].b;
}
sort(stu,stu+n,cmp);
long long sum=;
for(int i=;i<n;i++){
sum+=stu[i].a*(i+-)+stu[i].b*(n-i-);
//cout<<sum<<endl;
}
cout<<sum<<endl;
return ;
}