B. Group Photo 2 (online mirror version)
time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Many years have passed, and n friends met at a party again. Technologies have leaped forward since the last meeting, cameras with timer appeared and now it is not obligatory for one of the friends to stand with a camera, and, thus, being absent on the photo.
Simply speaking, the process of photographing can be described as follows. Each friend occupies a rectangle of pixels on the photo: the i-th of them in a standing state occupies a wi pixels wide and a hi pixels high rectangle. But also, each person can lie down for the photo, and then he will occupy a hi pixels wide and a wi pixels high rectangle.
The total photo will have size W×H, where W is the total width of all the people rectangles, and H is the maximum of the heights. The friends want to determine what minimum area the group photo can they obtain if no more than n/2 of them can lie on the ground (it would be strange if more than n/2 gentlemen lie on the ground together, isn’t it?..)
Help them to achieve this goal.
Input The first line contains integer n (1≤n≤1000) — the number of friends.
The next n lines have two integers wi,hi (1≤wi,hi≤1000) each, representing the size of the rectangle, corresponding to the i-th friend.
Output Print a single integer equal to the minimum possible area of the photo containing all friends if no more than n/2 of them can lie on the ground.
Sample test(s) input 3 10 1 20 2 30 3 output 180 input 3 3 1 2 2 4 3 output 21 input 1 5 10 output 50
思路题。
1.枚举最高的人是第
2.扫描剩下的++，，表明这个人必须躺下
3.如果，说明m这个高度一定不能当最高的，返回第一步继续枚举
4.在上述过程中，我们同时求出。 如果再让一些人躺下，可以使变小，使答案更优。 除了必须要躺下的这个人就变成最高的了。 我们把中就是对答案的优化了。
注意：一开始这个题WA了，因为最高的高度m可能是某个人的w，即让他躺下的高度。。
;int n;struct data{int w,h;}a[1005];priority_queue<int,vector<int>,greater<int> >q;int main(){scanf(“%d”,&n);for (int i=1;i<=n;i++)scanf(“%d%d”,&a[i].w,&a[i].h);int ans=1e9+5;for (int i=1;i<=n;i++){int m=a[i].h,now=a[i].w,cnt=0;for (int j=1;j<=n;j++){if (j!=i&&a[j].h>m)cnt++;if (a[j].h>m&&a[j].w>m)cnt=n+5;}if (cnt<=n/2){for (int j=1;j<=n;j++)if (j!=i){if (a[j].h>m) now+=a[j].h;else{now+=a[j].w;if (a[j].w<=m)q.push(a[j].h-a[j].w);}}while (cnt<n/2&&!q.empty()){int x=q.top();if (x>=0) break;now+=x;q.pop();cnt++;}while (!q.empty())q.pop();ans=min(ans,m*now);}m=a[i].w,now=a[i].h,cnt=1;for (int j=1;j<=n;j++){if (j!=i&&a[j].h>m)cnt++;if (a[j].h>m&&a[j].w>m)cnt=n+5;}if (cnt>n/2) continue;for (int j=1;j<=n;j++)if (j!=i){if (a[j].h>m) now+=a[j].h;else{now+=a[j].w;if (a[j].w<=m)q.push(a[j].h-a[j].w);}}while (cnt<n/2&&!q.empty()){int x=q.top();if (x>=0) break;now+=x;q.pop();cnt++;}while (!q.empty())q.pop();ans=min(ans,m*now);}printf(“%d\n”,ans);return 0;}D. Social Network
time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Polycarpus got an internship in one well-known social network. His test task is to count the number of unique users who have visited a social network during the day. Polycarpus was provided with information on all user requests for this time period. For each query, we know its time… and nothing else, because Polycarpus has already accidentally removed the user IDs corresponding to the requests from the database. Thus, it is now impossible to determine whether any two requests are made by the same person or by different people.
明天是世上增值最快的一块土地，因它充满了希望
