过不了
by S00021 @ 2021-11-08 19:44:42
稍微加了点数学，现在有60分了
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
long long t,n,c[50005],c1[50005],s1,s,ans;
struct lwt
{
long long a;
long long b;
}game[50005],game1[50005];
bool cmp(lwt a,lwt b)
{
return a.a<b.a;
}
bool cmp1(lwt a,lwt b)
{
return a.b<b.b;
}
void sa();
long long get();
int main()
{
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>t;
while(t--)
{
cin>>n;
for(long long i=1;i<=n;++i)
{
cin>>game[i].a>>game[i].b;
game1[i].a=game[i].a;
game1[i].b=game[i].b;
}
sort(game+1,game+n+1,cmp);
sort(game1+1,game1+n+1,cmp1);
ans=99999999999LL;
s=0;
for(long long i=1;i<=n;++i)
c[i]=0;
for(long long i=1;i<=n;++i)
{
s+=game[i].a;
c[i]+=max(c[i-1],s)+game[i].b;
}
s1=0;
for(long long i=1;i<=n;++i)
c1[i]=0;
for(long long i=1;i<=n;++i)
{
s1+=game1[i].a;
c1[i]+=max(c1[i-1],s1)+game1[i].b;
}
ans=min(c[n],c1[n]);
long long ctrl=253;
while(ctrl--)
sa();
printf("%lld\n",ans);
}
return 0;
}
long long get()
{
s=0;
for(long long i=1;i<=n;++i)
c[i]=0;
for(long long i=1;i<=n;++i)
{
s+=game[i].a;
c[i]+=max(c[i-1],s)+game[i].b;
}
s1=0;
for(long long i=1;i<=n;++i)
c1[i]=0;
for(long long i=1;i<=n;++i)
{
s1+=game1[i].a;
c1[i]+=max(c1[i-1],s1)+game1[i].b;
}
return min(c[n],c1[n]);
}
void sa()
{
double begin1=2303,end1=1e-5,change1=0.4218;
for(double i=begin1;i>end1;i*=change1)
{
long long x=rand()%n+1,y=rand()%n+1;
swap(game[x].a,game[y].a);
swap(game[x].b,game[y].b);
swap(game1[x].a,game1[y].a);
swap(game1[x].b,game1[y].b);
long long sum=get();
if(sum<ans)
ans=sum;
else
{
if(exp((ans-sum)/i)<(double(rand())/RAND_MAX))
{
swap(game[x].a,game[y].a);
swap(game[x].b,game[y].b);
swap(game1[x].a,game1[y].a);
swap(game1[x].b,game1[y].b);
}
}
}
}
```
by Lqwq @ 2021-11-08 21:03:51
70分了 感觉再加点简单的数学就能过了
今天 我一定要用 模拟退火 a了这道题！
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
long long t,n,c[50005],c1[50005],s1,s,ans;
struct lwt
{
long long a;
long long b;
}game[50005],game1[50005];
bool cmp(lwt a,lwt b)
{
return a.a<b.a;
}
bool cmp1(lwt a,lwt b)
{
return a.b<b.b;
}
void sa();
long long get();
int main()
{
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>t;
while(t--)
{
cin>>n;
for(long long i=1;i<=n;++i)
{
cin>>game[i].a>>game[i].b;
game1[i].a=game[i].a;
game1[i].b=game[i].b;
}
sort(game+1,game+n+1,cmp);
sort(game1+1,game1+n+1,cmp1);
ans=99999999999LL;
s=0;
for(long long i=1;i<=n;++i)
c[i]=0;
for(long long i=1;i<=n;++i)
{
s+=game[i].a;
c[i]+=max(c[i-1],s)+game[i].b;
}
s1=0;
for(long long i=1;i<=n;++i)
c1[i]=0;
for(long long i=1;i<=n;++i)
{
s1+=game1[i].a;
c1[i]+=max(c1[i-1],s1)+game1[i].b;
}
ans=min(c[n],c1[n]);
long long ctrl=173;
while(ctrl--)
sa();
printf("%lld\n",ans);
}
return 0;
}
long long get()
{
s=0;
for(long long i=1;i<=n;++i)
c[i]=0;
for(long long i=1;i<=n;++i)
{
s+=game[i].a;
c[i]+=max(c[i-1],s)+game[i].b;
}
s1=0;
for(long long i=1;i<=n;++i)
c1[i]=0;
for(long long i=1;i<=n;++i)
{
s1+=game1[i].a;
c1[i]+=max(c1[i-1],s1)+game1[i].b;
}
return min(c[n],c1[n]);
}
void sa()
{
double begin1=1813,end1=1e-5,change1=0.3978;
for(double i=begin1;i>end1;i*=change1)
{
long long x=rand()%n+1,y=rand()%n+1;
swap(game[x].a,game[y].a);
swap(game[x].b,game[y].b);
swap(game1[x].a,game1[y].a);
swap(game1[x].b,game1[y].b);
long long sum=get();
if(sum<ans)
ans=sum;
else
{
if(exp((ans-sum)/i)<(double(rand())/RAND_MAX))
{
swap(game[x].a,game[y].a);
swap(game[x].b,game[y].b);
swap(game1[x].a,game1[y].a);
swap(game1[x].b,game1[y].b);
}
}
}
}
```
by Lqwq @ 2021-11-08 21:11:18
~~又一个被模拟退火引上邪路的可怜娃~~
by 小林伊吕波 @ 2021-11-08 21:13:20
感觉优化着优化着就会数学解了。最后的版本跟数学解好像相差无几
by Lqwq @ 2021-11-09 07:27:54
十组数据，很蓝的啦
by Lacrymabre @ 2022-05-05 17:28:27
~~已经结束啦~~！
by chlchl @ 2022-07-12 14:09:48
我随随便便写个随机算法都能得 95 分。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node{
int a,b;
}a[20010];
void knuth(){//knuth算法
for(int i=1;i<=n;i++)
swap(a[1],a[rand()%n+1]);
}
int count(){
int sum=0,ans=0;
for(int i=1;i<=n;i++){
sum+=a[i].a;
ans=max(ans,sum)+a[i].b;
}
return ans;
}
bool cmp(node x,node y){
return (min(x.a,y.b)<min(x.b,y.a)) ? 1 : 0;
}
void solve(){
srand(time(0));
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].a>>a[i].b;
sort(a+1,a+n+1,cmp);
int cnt=0,ans=2e15;
while(cnt+2*n<=1e7){//时间足够就继续枚举
cnt+=2*n;
int p=count();
ans=min(ans,p);
knuth();
}
cout<<ans<<"\n";
}
signed main() {
int t;
cin>>t;
while(t--) solve();
return 0;
}
```
by Libingyue2011 @ 2023-07-19 12:56:01