#include<iostream> #include<fstream> using namespace std; int t,size,count,a[201],b[201],c[201],p; int main(){ //streambuf *backup; // ifstream fin; // fin.open("data.in"); // backup = cin.rdbuf(); // back up cin's streambuf // cin.rdbuf(fin.rdbuf()); // assign file's streambuf to cin //streambuf *coutbuf = cout.rdbuf(); //ofstream fout; //fout.open("data.out"); //cout.rdbuf(fout.rdbuf()); cin>>t; while(t--){ cin>>size; int temp; for(int i=0;i<size;i++){ cin>>a[i]>>b[i]; a[i]=(a[i]+1)/2; b[i]=(b[i]+1)/2; if(a[i]>b[i]){ temp=a[i]; a[i]=b[i]; b[i]=temp; } } for(int i=0;i<size;++i) { for(int l=i+1;l<size;++l) { if(a[i]>a[l]) { p=a[i]; a[i]=a[l]; a[l]=p; p=b[i]; b[i]=b[l]; b[l]=p; } } } memset(c,0,sizeof(c)); count=0; while(1){ int index=-1; for(int i=0;i<size;i++){ if(c[i]==0){ if(index==-1){ index=i; c[index]=1; count++; }else{ if(a[i]>b[index]){ c[i]=1; index=i; } } } } if(index==-1) break; } cout<<count*10<<endl; } return 0; }
因为每次选择是可以有多种组合的,一开始在想dp,后来发现只要排序后从小到大来取,结果就是最优的。
写sort的时候用bubblesort还给写错了,耽误了时间。
看discuss有种最简单的方法是算重叠部分的最大值,就是结果。